[Java] 백준 12865 : 평범한 배낭

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

12865번: 평범한 배낭

---

N=4 k=7이고, 

물건 1 = 6 13
물건 2 = 4 8
물건 3 = 3 6
물건 4 = 5 12

일 때,  담을 수 있는 무게가 0일 때부터 7일 때까지 최대 가치를 찾으면 된다. 

 

물건 1번을 담게 되면 무게 6 가치 13 이기 때문에 0~5까지는 담을 수 없기 때문에 0, 6과 7에서는 1번 외에는 더 담을  수 없기 때문에 13이다. 

N\k	0	1	2	3	4	5	6	7
1	0	0	0	0	0	0	13	13
2
3
4

 

물건 2번을 담게 되면 무게 4 가치 8이기 때문에 0~3까지는 0이고 4와 5에서는 8인데 6과 7에서는 2번 물건을 담는 것보다는 1번 물건을 담는 것이 더 가치가 있으므로 13이다.

N\k	0	1	2	3	4	5	6	7
1	0	0	0	0	0	0	13	13
2	0	0	0	0	8	8	13	13
3
4

 

물건 3번을 담게 되면 무게 3 가치 6이기 때문에 0~2까지는 0, 3은 6 이지만 4와 5에서는 물건 2를 담는 게 더 가치 있으므로 8, 6은 1번을 담는 게 가치 있으므로 13이다. 여기서 중요한건 7인데, 여기는 3번을 넣고 4번을 넣는 것이 더 가치 있으므로 14이다. 무게가 남으며 더 넣을 수 있는 물건이 있을 때, 더 담지 않았을 때 가치 값 vs (현재 물건 가치  + 남은 무게 넣을 수 있는 물건 가치) 해서 더 최대 값을 대입해 주면 된다. 

N\k	0	1	2	3	4	5	6	7
1	0	0	0	0	0	0	13	13
2	0	0	0	0	8	8	13	13
3	0	0	0	6	8	8	13	14
4

표를 완성하면 

N\k	0	1	2	3	4	5	6	7
1	0	0	0	0	0	0	13	13
2	0	0	0	0	8	8	13	13
3	0	0	0	6	8	8	13	14
4	0	0	0	6	8	12	13	14

 

물건 3번의 무게 7일 때의 점화식은 dp[i][j] = Math.max(dp [i-1][j], dp [i-1][j-w [i]]+v [i]);이다. 

 

---

import java.io.*;
import java.util.*;

public class Main {
	
	static int N,K;
	static int[][] dp;
	static int[] w,v;
	
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();	//물품의 개수 
		K = sc.nextInt();	//버틸 수 있는 무게
		
		w = new int[N+1];
		v = new int[N+1];
		dp= new int[N+1][K+1];
		
		for(int i=1;i<=N;i++) {
			w[i]=sc.nextInt();	//무게
			v[i]=sc.nextInt();	//가치 
		}
		
		for(int i=1;i<=N;i++) {
			for(int j=1;j<=K;j++) {
				dp[i][j]=dp[i-1][j];
				if(j - w[i]>=0) { 
					dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-w[i]]+v[i]);
				}
			}
		}
				
		System.out.println(dp[N][K]);
		
	}// main()
	

}// class Main