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

12865번: 평범한 배낭

문제

입력으로 주어지는 N개의 물건들은 각각 무게 W와 가치 V를 가진다. 배낭이 최대 K의 하중을 견딜 수 있다고 할 때, 무게의 합이 K를 넘지 않으면서 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 구한다.

 

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

DP의 bottom up 방식에서는 이전 값을 활용하여 현재 값을 구한다.  dp[i][j]는 무게 제한이 j일 때의 i번째 물건까지의 가치의 최대값인데, 우선 for문을 통해 무게제한을 1부터 k까지 늘려가며 dp 배열에 하나씩 넣어본다. 이 때

1. 만약 그 물건의 무게가 현재 최대 무게 하중을 넘지 않는다면, i-1(이전값)에서 하중이 j일때(현재 하중일 때) 구한 최대값과 i-1의 j 위치에서 현재 하중만큼을 뺀(j-weight[i]) 자리에 i번째 물건을 넣었을 때의 값과 비교하여 더 큰 것을 dp에 넣는다.
2. 물건의 무게가 최대 무게 하중을 넘는다면, 배낭에 넣을 수 없는 것이므로 이전 값을 dp에 넣는다.

이는 DP 방식으로 문제를 해결하기 위해 각 무게당 넣을 수 있는 무게에 대해 최대 가치를 생각해보며 푸는 방법이다. 만약 dp[i-1][j]가 더 큰 값이라면 현재 i번째 물건을 넣을 필요가 없는 것이고, dp[i-1][j-weight[i]]+price[i]가 더 큰 값이라면 현재 i번째 물건을 포함시킨 값이 현재까지의 최대값이라는 뜻이다.

소스코드

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];
    }
}