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

문제

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

 

풀이

[Algorithm] 동적 계획법(Dynamic Programming)

을 참고해서 풀이를 작성하겠다.

 

1. 어려운 문제가 될 수 있는 요소 찾기

물건

무게(w)

가치(v)

준서가 넣는 물건들 중 k 이하의 무게로 넣었을때 얻을 수 있는 최대의 가치이다.

결국 어려운 문제가 되려면 물건을 고르고, 최대 무게(w)가 되었을때가 어려운 문제라고 말할 수 있을 것이다.

최대 무게

물건을 고름

 

2. 테이블 정의

dp[i][j] = i번째 물건을 넣었을 때, 정확히 j의 무게로 담았을 때의 최대 가치로 정의했다.

 

3. 정의한 테이블에서 정답을 찾기

물건이 n개 있다고 한다면, n개의 물건을 넣은 dp[i][0] ~ dp[i][k] 까지의 가치들중 최대 가치를 구하면 된다고 생각했다.

 

4. 정의한 테이블에서 초기화

물건을 아예 넣지 않은 경우에 대해 담았을 경우, 얻을 수 있는 가치는 0인데,

java에서 int 배열을 선언하면 기본적으로 0이므로, 초기화 로직이 없어도 된다.

 

5. 점화식 도출

이 문제에서 물건을 넣는가/물건을 안넣는가가 문제에 상황에서 변화될 수 있는 요소이다.

 

물건을 넣지 않는다면

=> dp[i - 1][j] : 정확히 j 무게로 담는데, i - 1번의 물건을 담았을 경우의 가치

 

물건을 넣는 다면

=> dp[i - 1][j - w] + v : 물건에는 무게가 있다. 그러면 기존 가방에 대한 무게는 담는 물건에 대한 무게를 뺀,  j - w가 될 것이고, 물건을 담지 않았기 때문에, dp[i - 1][j - w]이다 여기에 가치(v)를 더한 가치이다.

 

주의

j - w가 0보다 작을 수도 있다. 현재 가방의 무게보다 물건의 무게가 더 커질 수 있으므로, 0보다 작아질 수 있음에 유의한다.

 

그래서 dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 무게] + 가치)이다.

 

소스코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

import java.util.StringTokenizer;

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[] w = new int[n + 1];
        int[] v = new int[n + 1];

        for (int i = 1; i < n + 1; i++) {
            st = new StringTokenizer(br.readLine(), " ");

            w[i] = Integer.parseInt(st.nextToken());
            v[i] = Integer.parseInt(st.nextToken());
        }

        int[][] dp = new int[n + 1][k + 1];

        for (int i = 1; i < n + 1; i++) {
            for (int j = 1; j < k + 1; j++) {
                dp[i][j] = dp[i - 1][j];

                //j의 무게를 담을 수 있는 가방에서, 무게를 넣을 수 있을 때,
                if (j - w[i] >= 0) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - w[i]] + v[i]);
                }
            }
        }

        int answer = Integer.MIN_VALUE;

        for (int value : dp[n]) {
            answer = Math.max(value, answer);
        }

        System.out.print(answer);

        br.close();
    }
}