EunSung.log

평범한 배낭

3 min read

문제 정보

풀이

DP의 대표적인 문제인 0-1 Knapsack 문제다.

최대 가치합을 구하려면 두 가지 정보가 필요하다. 어떤 물건까지 고려했는지와, 현재까지 사용한 무게가 얼마인지다.

물건을 하나씩 순서대로 고려하면서, 각 무게 제한에서의 최대 가치합을 저장하면 이전 단계의 결과를 재사용할 수 있다.

따라서 dp[i][j]를 i번째 물건까지 고려했을 때 무게 제한이 j인 경우의 최대 가치합으로 정의한다.

dp[i][j]를 구할 때 i번째 물건을 배낭에 담을지 여부로 경우를 나눌 수 있다.

  1. i번째 물건의 무게 가 j보다 큰 경우
    • 무게 제한 j를 초과하므로 i번째 물건을 담을 수 없다. 그러므로 i-1번째까지의 결과를 그대로 유지한다.
    • → dp[i][j] = dp[i - 1][j]
  2. i번째 물건의 무게 가 j이하인 경우
    • i번째 물건을 담을 수 있으므로 담는 경우와 담지 않는 경우 중 더 큰 값을 선택한다.
      • 담지 않는 경우: i번째 물건을 제외한 상태의 최대 가치합 → dp[i - 1][j]
      • 담는 경우: i번째 물건을 담기 전, 즉 무게가 일 때의 최대 가치합에 를 더한다 → `dp[i - 1][j - w] + v
    • → dp[i][j] = max(dp[i -1][j], dp[i - 1][j - w] + v)

코드

import java.io.*;
import java.util.*;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        
        int[][] item = new int[n + 1][2];
        for (int i = 1; i <= n; i++) {
            st = new StringTokenizer(br.readLine());
            item[i][0] = Integer.parseInt(st.nextToken());
            item[i][1] = Integer.parseInt(st.nextToken());
        }
        
        int[][] dp = new int[n + 1][k + 1];
        for (int i = 1; i <= n; i++) {            
            for (int j = 1; j <= k; j++) {
                int w = item[i][0];
                int v = item[i][1];
                
                if (w > j)
                    dp[i][j] = dp[i - 1][j];
                else
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - w] + v);
            }
        }
        
        System.out.println(dp[n][k]);
    }
}

백링크