[BOJ 12865] 평범한 배낭(Java, DP)

https://www.acmicpc.net/problem/12865

12865번: 평범한 배낭

 

 

1. 전체 물품을 이용해서, 제시된 K 무게까지의 최대 가치를 구해야 한다. 소문제로 나누어서 문제를 풀기 위해서, 두 가지 변수를 사용한다. 물품과 무게를 사용해서 DP를 구성한다.

 

 

 

 

2. DP의 점화식을 세워야 하는데, DP[i][j] = max(DP[i - 1][j] + DP[i - 1][j - i번째 물품 무게] + i번째 가치)

*위의 식을 말로 풀어서 설명하자면, i번째 물품까지 쓸 수 있을 때, j무게까지의 최댓값은 i번째 물품(i - 1) 이전 최댓값이거나 i번째 물품을 추가했을 때의 값 중 큰 값이 된다.

 

 

 

---

 

해설코드(Java).

import java.util.*;
import java.lang.*;
import java.io.*;
 
class Item
{
    int W, V;
    public Item(int W, int V){
        this.W = W;
        this.V = V;
    }
}
 
class Main
{
    public static void main (String[] args) throws java.lang.Exception
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String[] sArr = br.readLine().split(" ");
        ArrayList<Item> aList = new ArrayList<>();
        
        int N = Integer.valueOf(sArr[0]);
        int K = Integer.valueOf(sArr[1]);
        int[][] dp = new int[N + 1][K + 1];
        
        aList.add(new Item(0, 0));
        for(int i = 0; i < N; i++){
            sArr = br.readLine().split(" ");
            int w = Integer.valueOf(sArr[0]);
            int k = Integer.valueOf(sArr[1]);
            aList.add(new Item(w, k));
        }
        
        int answer = 0;
        for(int i = 1; i <= N; i++){
            Item item = aList.get(i);
            for(int j = 1; j <= K; j++){
                dp[i][j] = dp[i - 1][j];
                if(j - item.W >= 0){
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - item.W] + item.V);
                }
                answer = Math.max(answer, dp[i][j]);
            }
        }
        
        bw.write(answer + "\n");
        bw.flush();
    }
}