백준 12865

문제

---

dp[N][K] : 주어진 물품의 수가 N개, 선택할 수 있는 물품의 총 무게는 K 이내일 때 선택한 물품의 최대 가치의 합

1) N 번째 물품의 무게가 K보다 클 때
- dp[N-1][K]와 같을 것 (어차피 N번째 물품은 못 넣으니까...)

2) N 번째 물품의 무게가 K보다 작을 때
2 - 1) N 번째 물품을 포함할 때
2 - 2) N 번째 물품을 포함하지 않을 때

위의 3가지 경우 중 하나이다.

분기를 나눠서 1)일 경우 2)일 경우로 나누고

2)일 경우는 2 - 1)과 2 - 2) 중 더 큰 가치를 갖는 쪽으로 선택.

---

Code

package test;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class P12865 {

	private static int[][] things;
	private static Integer[][] dp;
	
	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());
		
		things = new int[N + 1][2];
		dp = new Integer[N + 1][K + 1];
        
		for(int i = 1; i <= N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			things[i][0] = Integer.parseInt(st.nextToken()); // Weight
			things[i][1] = Integer.parseInt(st.nextToken()); // Value
		}
		System.out.println(worthOfBag(N, K));
	}
	
	private static int worthOfBag(int i, int k) {
		if(i <= 0) {
			return 0;
		}
		if(dp[i][k] == null) {
			
			if(things[i][0] > k) {
				dp[i][k] = worthOfBag(i - 1, k);
			} 
			
			else {
				dp[i][k] = Math.max(
						worthOfBag(i - 1, k), 
						worthOfBag(i - 1, k - things[i][0]) + things[i][1]);	
			}
		}
		return dp[i][k];
	}

}