[백준/JAVA] 12865: 평범한 배낭

[백준/JAVA] 12865: 평범한 배낭

N개의 물건이 있고 각 물건은 W의 무게와 V의 가치를 가진다. 이때 물건들의 가치를 최대화하면서 무게제한인 K를 넘지 않도록 물건을 고르는 경우의 수를 찾는다.

이 문제는 다이나믹 프로그래밍에서 유명한 알고리즘 문제인 knapsack 문제이다. 브루트 포스로 풀 수도 있고 재귀를 사용할 수도 있는데, 당연하지만 DP를 사용하는 방법이 제일 시간복잡도가 낮은 방법이다.

knapsack 함수에서 for문을 돌며 무게제한을 1부터 k까지 점점 증가시켜나간다. 이때 이전값과 비교하여 가치가 더 높아진다면 값을 교체한다. 만약 i번째 물건이 현재 무게제한을 넘어선다면 i번째 물건은 배낭에 넣을 수 없으므로 i-1번째 물건까지의 가치의 합으로 바꾼다.

(참고) 인덱스를 1부터 시작하는 이유는 k의 사용을 쉽게 하기 위해서이다.

소스코드

---

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

public class Main {
	public static int n, k;
	public static int weight[], price[], dp[][];
    public static void main(String[] args) throws IOException {
        BufferedReader br = 
        		new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());
        
        // 인덱스 1부터 시작
        weight = new int[n+1];
        price = new int[n+1];
        for (int i=1; i<=n; i++) {
        	st = new StringTokenizer(br.readLine());
        	weight[i] = Integer.parseInt(st.nextToken());
        	price[i] = Integer.parseInt(st.nextToken());
        }
        
        dp = new int[n+1][k+1]; // dp[i][j]는 무게 제한이 j일때의 i번째 물건까지의 최대 가치이다
        System.out.println(knapsack());
    }
    
    public static int knapsack() {
    	/* 1부터 n까지의 물건에 대해 무게제한을 1부터 k까지 반복하며
    	 * 현재 물건이 그 무게제한보다 작다면 그 물건을 배낭에 넣는다.
    	 * 무게제한을 작은것부터 시작하여 더 무게가 작은 물건을 먼저 넣게 되고
    	 * k까지 반복하면서 가치가 더 높은 쪽을 선택한다.
    	 */
    	for(int i=1; i<=n; i++)
    		for (int j=1; j<=k; j++) {
    			if (weight[i] <= j)
    				// 이전값(i-1,j)과 현재값(i번째 물건을 포함시킨 경우)중 가치가 큰것을 선택
    				dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-weight[i]]+price[i]);
    			else
    				// 현재 i번째 물건이 k를 넘어선다면 이전 값을 사용해야 한다
    				dp[i][j] = dp[i-1][j];
    		}
    	return dp[n][k];
    }
}