골드에그

1. 문제요약

12865번: 평범한 배낭 (acmicpc.net)

주인공의 배낭은 최대 K 크기 만큼 물건을 넣을 수 있다. 배낭에 넣을 수 있는 물건들의 무게와 가치가 주어질 때, 배낭에 넣을 수 있는 물건들의 가치 최댓값을 출력하시오.

2. 문제예제

3. 팩트추출

"워낙 유명한 문제라 DP 알고리즘 문제라는 것을 알고 문제를 푸는 것이 아니라

어떻게 DP 로 접근했을까 생각하고 아이디어를 정리해보았다."

Fact 1 : 각 물건들을 고르거나 고르지 않는 모든 경우의 수를 고려해보면 쉽게 문제를 해결할 수 있다. 하지만, O(2^N) 시간복잡도가 필요하며 너무 많은 시간이 소요된다. 물건이 하나씩 추가될 때마다 기존 시간의 2배 정도 시간이 필요한 것이다. 물건에만 포커스를 맞춘 경우인데 이러한 구조는 이미 경우의 수 일부에서 배낭이 꽉 찬 경우인데도 어쩔 수 없이 탐색할 수 밖에 없다. 위 예제 1에서 첫 번째 아이템을 선택하면 무게가 6으로 그 다음은 7-6=1무게만큼 필요한데 1무게를 찾기 위해서 모든 조합을 다 찾아야 한다는 것이다. 여기서 힌트를 얻을 수 있다.

내가 지금 필요한 무게에 대한 최대값을 바로 찾을 수 있다면 그런 수고를 덜 수 있다. 위 예제에서는 1무게에 대한 최대값 말이다. 다시 말해 물건과 무게 두 곳에 포커스를 맞추어 정답을 구하는 것이다.

Fact 2 : i 번째 물건까지 보았을 때 가치가 최대인 무게들을 구한다는 것은 부분문제처럼 보인다. 여기서 구하려고 하는 최종 결과값도 최대 가치를 만들려고 하는 것이기 때문이다. 부분 문제이고 작은 문제들의 정답이 다음 문제들에게 영향을 미친다면 DP (Dynamic Programming) 문제이다. DP[i][j] 를 i 번째 물건까지 보았을 때 j 무게에서 최대 가치라고 할 때 아래와 같은 수식이 만족한다.

DP[i][j] = max(v[i] + dp[i-1][j - w[i]], dp[i-1][j])

각 가방의 가치 : v[n] / 각 가방의 무게 : w[n]

dp[i-1][j] 는 이전 물건까지만 고르고 현재 물건을 고르지 않는 경우이고, v[i] + dp[i-1][j-w[i]] 는 이전 물건도 고르고 이번 물건도 고르는 경우이다. j-w[i] 수식을 보면 배낭의 남은 무게보다 현재 물건의 무게가 작아야 한다는 것을 알 수 있다. 물건을 탐색했을 때 가방에 넣을 수 있다면 해당 무게로 이전까지 선택한 최대치에 현재 가치를 더해서 최대치를 갱신한다.

Fact 3 : 점화식도 분명 현재 물건을 넣는 경우와 넣지 않는 경우의 수가 필요한 것이 분명한데 O(2^N) 이 되지 않는 점을 이해해야 한다. 모든 조합의 경우의 수를 구해서 문제를 푸는 것이 아니라 각 단계마다 정답을 구해 이전 경우의 수를 상쇄시키는 것이 특징이다. 이전 값만 보고 판단한다. DP 특징이기도 하다. 또한 해당 시점에서 배낭의 무게를 1차이로 모두 구해 탐색하지 않고 바로 답을 구하는 것을 볼 수 있다.

4. 문제풀이(수동)

문제 예제 입력 1번의 DP 테이블을 만들었을 때 다음과 같다.

위 DP 점화식을 토대로 i 가 1부터 4까지 j 행을 차례로 구한다. 

dp[3][7] 을 살펴보면, dp[3][7] 은 dp[2][7] 과  dp[3][7-(3번 물건의 무게)] + v[3] 둘 중 큰 값을 저장하게 된다. dp[3][4] 값은 8이고 v[3] 은 6이므로 최종적으로 dp[2][7] 은 13, dp[3][7] 은 14이므로 dp[3][7] 에는 14가 저장된다.

5. 문제전략

문제 전략은 팩트 추출과 문제풀이(수동) 을 통해 알아보았다. 도출한 DP 방정식으로 문제를 풀었다.

6. 소스코드

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

public class Main {
    private static int N, K;
    private static int[] weight, value;
    private static int[] dp;
    private static void knapsack() {
        for (int i = 1; i <= N; i++) {
            for (int j = K; j - weight[i] >= 0; j--) {
                dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
            }
        }
    }

    public static void main(String[] args) throws IOException {
        StringTokenizer st;

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        weight = new int[N+1];
        value = new int[N+1];
        dp = new int[K+1];

        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            weight[i] = Integer.parseInt(st.nextToken());
            value[i] = Integer.parseInt(st.nextToken());
        }
        knapsack();
        System.out.println(dp[K]);
    }
}