[백준 12865번] 평범한 배낭

문제 링크: 12865번 평범한 배낭

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

 

DP 알고리즘 중에서도 Knapsack 알고리즘을 대표하는 문제이다. 며칠을 고민하다가 전 과정 풀이를 참고했다.

 

풀이를 본 이상 점화식을 이해하는 것은 생각보다 어렵지 않았다.

 

n개의 물품 중 고려하는 물품 번호가 1<=i<=n이고 배낭에 담을 수 있는 최대 무게가 w일 때의 최대 가치를 D(i, w)라고 하고, W(i)는 물품[i]의 무게를, V(i)는 물품[i]의 가치를 나타낸다고 하면, 다음과 같은 점화식을 만들 수 있다. 

 

D(i, w) =
D(i-1, w)          if w<W(i) // ①
max(D(i-1, w), D(i-1, w-W(i))+V(i))          else // ②

① 배낭에 물품[i]가 결코 들어갈 수 없다.

배낭에 담을 수 있는 최대 무게(w)가 물품[i]의 무게(W(i))보다도 작다면, 절대 담을 수 없기 때문이다.

 

② 배낭에 물품[i]가 들어갈 수도 있다. ②-1과 ②-2 중 보다 큰 값이 최대 가치가 된다.

②-1. 물품[i]가 들어가려면?

먼저 배낭에서 물품[i]의 무게만큼을 미리 비워둔다. 사용 가능한 가방의 무게 한도 내에서 물품[i-1]까지를 채웠을 때의 최대 가치(D(i-1, w-W(i))에 물품[i]의 무게(V(i))를 더하면, 이것이 최대 가치이다.

②-2. 물품[i]가 들어가지 않는다면?

최대 무게가 w일 때, 물품[i]까지 채웠을 때의 최대 가치는 물품[i-1]까지 채웠을 때의 최대 가치와 같다.

 

그런데 점화식을 보고서는 재귀적인 알고리즘 이외에는 구현 방식이 떠오르지 않았다. 이는 dp를 2차원 배열로서 선언하고, dp[i][w]는 i번째 물품까지에 대해서 최대 무게가 w일 때의 최대 가치를 저장하도록 하는 방법을 통해 해결할 수 있다. dp[i]에 대해서 w를 증가시켜가면서, w<arr[i].weight일 때 ①을 구현하고, 그 이후에는 ②를 구현한다.

 

import java.util.Scanner;

class Item {
    Item(int weight, int value) {
        this.weight = weight;
        this.value = value;
    }

    int weight;
    int value;
}

public class Main {
    public static void main(String[] args) {
        /* input */
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int maxWeight = sc.nextInt();

        Item[] arr = new Item[n+1];
        int[][] dp = new int[n+1][maxWeight+1];
        for (int i = 1; i <= n; i++) {
            int weight = sc.nextInt();
            int value = sc.nextInt();
            arr[i] = new Item(weight, value);
        }

        /* logic */
        for (int w = arr[1].weight; w <= maxWeight; w++)
            dp[1][w] = arr[1].value;

        for (int i = 2; i <= n; i++) {
            for (int w = 0; w <= maxWeight; w++) {
                // arr[i]가 포함될 수 없음
                if (w < arr[i].weight)
                    dp[i][w] = dp[i-1][w];
                // arr[i]가 포함될 수도 있음
                else
                    dp[i][w] = Math.max(dp[i-1][w], dp[i-1][w-arr[i].weight]+arr[i].value);
            }
        }

        System.out.println(dp[n][maxWeight]);
    }
}