백준 12865번 평범한 배낭 JAVA

링크텍스트

설명

예제입력으로 설명하겠다.
n=4, k=7

첫 번째 물건: 무게 6, 가치 13
dp[7] = max(dp[7], dp[7 - 6] + 13) = max(0, 0 + 13) = 13
dp[6] = max(dp[6], dp[6 - 6] + 13) = max(0, 0 + 13) = 13

두 번째 물건: 무게 4, 가치 8
dp[7] = max(dp[7], dp[7 - 4] + 8) = max(13, 0 + 8) = 13
dp[6] = max(dp[6], dp[6 - 4] + 8) = max(13, 0 + 8) = 13
dp[5] = max(dp[5], dp[5 - 4] + 8) = max(0, 0 + 8) = 8
dp[4] = max(dp[4], dp[4 - 4] + 8) = max(0, 0 + 8) = 8

세 번째 물건: 무게 5, 가치 6
dp[7] = max(dp[7], dp[7 - 5] + 12) = max(14, 0 + 12) = 14
dp[6] = max(dp[6], dp[6 - 5] + 12) = max(14, 0 + 12) = 14
dp[5] = max(dp[5], dp[5 - 5] + 12) = max(8, 0 + 12) = 12

코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        int[] dp = new int[k + 1];
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            int w = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());

            for (int j = k; j >= w; j--) {
                dp[j] = Math.max(dp[j], dp[j - w] + v);
            }
        }

        System.out.println(dp[k]); 
    }
}

참고 글

https://st-lab.tistory.com/141