[백준] 평범한 배낭 java

www.acmicpc.net/problem/12865

12865번: 평범한 배낭

문제 풀이 : 

배낭이 비어있는 상태에서 시작하여 물건을 하나씩 배낭에 담는 것을 현재 배낭에 들어있는 물건의 가치가 큰 것을 고르면서 배낭 용량의 무게를 검사해야합니다.

 

1. dp[i-1][j] : 물건 i를 포함하지 않습니다. 즉 그 전과 동일합니다.

2. dp[i-1][j-w[i]]+v[i] : 물건 i를 포함합니다. 물건 i의 가치 + 물건 1 ~(i-1) 까지 고려하여 현재 배낭의 용량이 (w-w(i))인 경우의 최대 가치입니다.

즉 1번 2번이 미리 계산 되어 있어야 dp[i][j]를 구할 수 있습니다.

 

i	w	v
1	6	13
2	4	8
3	3	6
4	5	12

 

i                       0  1  2  3  4  5  6  7

0  고려할 물건    [0, 0, 0, 0, 0, 0, 0, 0]
1  {1}                [0, 0, 0, 0, 0, 0, 13, 13] 
2  {1,2}              [0, 0, 0, 0, 8, 8, 13, 13]
3  {1,2,3}            [0, 0, 0, 6, 8, 8, 13, 14]
4  {1,2,3,4}          [0, 0, 0, 6, 8, 12, 13, 14]

 

import java.util.Scanner;

public class Main{
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int K = sc.nextInt();
		
		int[] W = new int[N+1];//무게
		int[] V = new int[N+1];//가치
		int[][] dp = new int[N+1][K+1];

		for (int i = 1; i < N+1; i++) {
			W[i] = sc.nextInt();
			V[i] = sc.nextInt();
		}//end of input

		for (int i = 1; i < N+1; i++) {
			for (int j = 1; j < K+1; j++) {
				if(W[i] > j) dp[i][j] = dp[i-1][j];//i 번째 물건 담을 수 없음
				else dp[i][j] = Math.max(dp[i-1][j-W[i]]+V[i], dp[i-1][j]);//i 번째 물건 가능
				
			 	
			}
		}
		
		System.out.println(dp[N][K]);
		
		
	}
}