백준 12865 - 평범한 배낭

Java

12865 번 - 평범한 배낭

문제

준서가 여행에 필요하다고 생각하는 N개의 물건이 있다.
각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다.
아직 행군을 해본 적이 없는 준서는 최대 K만큼의 무게만을 넣을 수 있는 배낭만 들고 다닐 수 있다.
준서가 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 알려주자.

물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다.

무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)가 주어진다.

접근 방법

0/1 Knapsack Problem 알고리즘을 실제 문제에 적용하여 공부하였다.

코드

import java.util.*;
import java.io.*;

public class Main {
	static int n,k;
	static int[][] stock, bag;
    public static void main(String []args) throws IOException {        
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer stk = new StringTokenizer(br.readLine()); 
    	n = stoi(stk.nextToken());
    	k = stoi(stk.nextToken());
    	stock = new int[n + 1][2];
    	bag = new int[n + 1][k + 1];
    	
    	for(int i = 0; i < n; i++) {
    		stk = new StringTokenizer(br.readLine());
    		
    		stock[i + 1][0] = stoi(stk.nextToken());	// 물건의 무게
    		stock[i + 1][1] = stoi(stk.nextToken());	// 물건의 가치
    	}
    	/* 
    	 * 1. 물건을 0개 ~ n개 선택하는 경우마다 무게 0 ~ k의 경우를 다 확인
    	 * 2. 선택한 물건보다 현재까지의 무게가 더 작은 경우, 윗 단계 물건의 값에서 가져온다
    	 * 3. 현재 선택한 물건을 넣을 수 있으면, 현재 무게 j에서 선택한 물건 무게를 뺀 값에서의 최대 효율에서 더한 것과, 물건을 넣지 않을 때의 효율을 비교하여 큰 값을 넣는다.
    	 * 
    	*/
    	Arrays.fill(bag[0], 0);
    	int w, v;
    	for(int i = 1; i <= n; i++) {
    		for(int j = 1; j <= k; j++) {
    			w = stock[i][0];
    			v = stock[i][1];
    			if(j < w) {
    				bag[i][j] = bag[i - 1][j];
    			}
    			else {
    				bag[i][j] = Math.max(bag[i - 1][j], bag[i - 1][j - w] + v);
    			}
    		}
    	}
    	
    	System.out.println(bag[n][k]);
    	br.close();
    }
    static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

총평

난이도

⭐⭐★★★

후기

개선할 점