0-1 KnapSack

출처 : https://www.acmicpc.net/problem/12865
평범한 배낭 문제

무게(W)	가치(V)
6	13
4	8
3	6
5	12

배낭에 담을 수 있는 아이템의 최대 무게가 7이라고 하면
최대 무게(7)부터 현재 아이템의 무게까지 비교.
현재 아이템의 Index를 i,
최대 무게(7)부터 j >= W[i]의 무게를 담을 수 있다.

dp[j] = Math.max(dp[V[i]+dp[j-w[i]], dp[j]);

        for(int i=1; i<=N; i++){
            for(int j=M; j>=W[i]; j--){
                dp[j] = Math.max(V[i]+dp[j-W[i]], dp[j]);
            }    
        }

i = 1 / W[1] = 6 / V[1] = 13
dp[7] = 13+0 vs 0

1	2	3	4	5	6	7
0	0	0	0	0	0	13

=>
dp[6] = 13+0 vs 0

1	2	3	4	5	6	7
0	0	0	0	0	13	13

---

i = 2 / W[2] = 4 / V[2] = 8

dp[7] = 8+0 vs dp[7] : 13

1	2	3	4	5	6	7
0	0	0	0	0	13	13

dp[6] = 8+0 vs dp[6] : 13

1	2	3	4	5	6	7
0	0	0	0	0	13	13

dp[5] = 8+0 vs dp[5] : 0

1	2	3	4	5	6	7
0	0	0	0	8	13	13

---

이런식으로 값을 채워 넣으면
각 무게에 해당하는 최댓값을 구할 수 있다.

1	2	3	4	5	6	7
0	0	6	8	12	13	13