백준 12865 평범한 배낭 자바

문제는 다음과 같다.
https://www.acmicpc.net/problem/12865

풀이는 다음과 같다.

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));



        StringTokenizer st1 = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st1.nextToken()); //물건수
        int K = Integer.parseInt(st1.nextToken()); //무게제한


        int[] W = new int[N+1]; //index 번째 물건 무게
        int[] V = new int[N+1]; //index 번째 물건 가치

        int[] dp = new int[K+1];

        for(int i = 1 ; i <= N ; i++) {
            StringTokenizer st2 = new StringTokenizer(br.readLine());
            W[i] = Integer.parseInt(st2.nextToken());
            V[i] = Integer.parseInt(st2.nextToken());
        }
        
        for(int i = 1 ; i <= N ; i++) { //물건마다
            for(int j = K ; j - W[i] >= 0 ; j--) { //무게 제한 K부터 작은대로 j 무게마다
                dp[j] = Math.max(dp[j], dp[j-W[i]] + V[i]); 
                //기존의 j 무게까지의 가치 최댓값과, dp[j-W[i]] + V[i] (i번째 물건으로 j-W[i] 무게의 최댓값을 갱신해주기)
                //두 값중 최댓값으로 갱신
            }
        }

        bw.write(String.valueOf(dp[K]));
        bw.flush();
        bw.close();

    }

}

이전에 비스무리한 배낭에 넣는 문제를 풀었었는데,
https://velog.io/@dlsrjsdl6505/%EB%B0%B1%EC%A4%80-1202-%EB%B3%B4%EC%84%9D%EB%8F%84%EB%91%91-%EC%9E%90%EB%B0%94

해당 문제는 배낭에 공간이 여러개 있고,
해당 공간마다 수용가능한 무게가 다를때
최대의 가치를 지니도록
1개의 물건씩 공간에 넣는 문제였다면, (그리디)

이 문제는 가방의 공간은 하나이고, 여러 개를 넣어도 되니 무게 제한 안에서 최대의 가치를 지니도록 가방에 넣는 문제이다. (DP)

두개를 푸는 방법은 다르다.
하지만 나는 비스무리한 배낭 문제라서,
이번 문제도 그저 그리디 문제인줄 알고
혼자 무게 가벼운순, 가치 높은순으로 우선순위 큐를 구현하고.. 틀리고 그랬다.

이 문제는 DP 문제이다.

dp[j] = j 무게까지 넣었을때, 가능한 가치들 중 최댓값 이라고 지정하고 풀었다.
아래 부분이 핵심이다.

for(int i = 1 ; i <= N ; i++) { 
			//i번째 물건의 무게는 W[i], 가치는 V[i]이다.
            
            for(int j = K ; j - W[i] >= 0 ; j--) { //무게 제한 K부터 작은대로 j 무게마다
                dp[j] = Math.max(dp[j], dp[j-W[i]] + V[i]); 
                //기존의 j 무게까지의 가치 최댓값과, dp[j-W[i]] + V[i] (i번째 물건으로 j-W[i] 무게의 최댓값을 갱신해주기)
                //두 값중 최댓값으로 갱신
            }
        }

로직은,
N개의 물건중 하나를 물건을 잡는다.
for문의 i, 무게 W[i], 가치 V[i]

무게 j마다
for문의 j

무게 제한점 K부터 1씩 줄여나가며
2번째 for문의 for(int j = K ; j - W[i] >= 0 ; j--)

해당 물건으로 구현할 수 있는 가치의 최댓값을 갱신해준다.
dp[j] = Math.max(dp[j], dp[j-W[i]] + V[i]);

---

예시를 들겠다.
무게제한 7
물건1 무게 3 가치 6
물건2 무게 4 가치 8
이라고 하자.

W = {3, 4}
V = {6, 8}
dp = {0, 0, 0, 0, 0, 0, 0}

---

1번 for문
W[1] = 3, V[1] = 6

j = 7일 때
dp[7] = Math.max(dp[7], d[7-3] + 6) = 6
dp = {0, 0, 0, 0, 0, 0, 6}

j = 6일 때
dp[6] = Math.max(dp[6], d[6-3] + 6) = 6
dp = {0, 0, 0, 0, 0, 6, 6}

j = 5일 때
dp[5] = Math.max(dp[5], d[5-3] + 6) = 6
dp = {0, 0, 0, 0, 6, 6, 6}

j = 4일 때
dp[4] = Math.max(dp[4], d[4-3] + 6) = 6
dp = {0, 0, 0, 6, 6, 6, 6}

j = 3일 때
dp[3] = Math.max(dp[3], d[3-3] + 6) = 6
dp = {0, 0, 6, 6, 6, 6, 6}

더이상은 j - W[i] >= 0 때문에 할 수 없다.

---

2번 for 문
W[2] = 4, V[2] = 8
dp = {0, 0, 6, 6, 6, 6, 6}

j = 7일 때
dp[7] = Math.max(dp[7], d[7-4] + 8) = 14
dp = {0, 0, 6, 6, 6, 6, 14}

j = 6일 때
dp[6] = Math.max(dp[6], d[6-4] + 8) = 8
dp = {0, 0, 6, 6, 6, 8, 14}

j = 5일 때
dp[5] = Math.max(dp[5], d[5-4] + 8) = 8
dp = {0, 0, 6, 6, 8, 14, 14}

j = 4일 때
dp[4] = Math.max(dp[4], d[4-4] + 8) = 8
dp = {0, 0, 6, 8, 8, 14, 14}

더이상은 j - W[i] >= 0 때문에 할 수 없다.

---

위와 같은 방식으로 dp가 채워져 정답을 뽑아낼 수 있게 된다.
dp[7] = 14