백준 12865 평범한 배낭 (Gold 5)

정답코드

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


public class Knapsack {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String input [] = br.readLine().split(" ");
		int N = Integer.parseInt(input[0]);
		int K = Integer.parseInt(input[1]);
		
        //물건들의 무게를 저장
		int [] W = new int[N+1];
        //물건들의 가치를 저장
		int [] V = new int[N+1];
		for(int i = 1; i < N+1; i++) {
			String [] in = br.readLine().split(" ");
			int w = Integer.parseInt(in[0]);
			int v = Integer.parseInt(in[1]);
			
			W[i] = w;
			V[i] = v;
			
			
		}
		
		int [][] DP = new int[N+1][K+1];
		
		for(int i = 1; i < N+1; i++) {
			for(int j = 1; j < K+1; j++) {
				if(j < W[i])DP[i][j] = DP[i-1][j];
				
				else if(j >= W[i])DP[i][j] = Math.max(DP[i-1][j], DP[i-1][j-W[i]]+V[i]);
			}
			
		}
		
		System.out.println(DP[N][K]);
		
	}

}

전략

• 지금 물건을 담을 때의 가치 값과 지금 물건을 담지 않을 때의 물건의 가치를 비교해서 더 큰 가치를 배낭에 넣는다

• i = 0 ~ W 까지 순회하면서 지금 무게에 이 물건을 넣을 수 없다면 이 물건을 제외한 DP값을 가진다

• 만약 지금 무게에 이 물건을 넣을 수 있다면 Max(이 물건을 넣지 않았을때, 지금무게 - 이 물건 무게에서 가질 수 있는 가치 + 지금 물건의 가치로 계산)