백준 12865 평범한 배낭 Java: 1차원 0/1 Knapsack DP

백준 12865번 ‘평범한 배낭’은 각 물건을 최대 한 번 선택해 무게 합이 K 이하일 때 가치 합을 최대로 만든다. 대표적인 0/1 knapsack 문제다.

• 백준 12865번 평범한 배낭

dp[capacity]를 지금까지 확인한 물건만 사용해 해당 무게 한도에서 얻을 수 있는 최대 가치로 두고, 물건마다 capacity를 큰 값부터 줄여 갱신하면 1차원 배열로 풀 수 있다.

점화식

현재 물건의 무게가 weight, 가치가 value라면 두 선택을 비교한다.

선택하지 않음: dp[capacity]
선택함:       dp[capacity - weight] + value

dp[capacity] = max(
    dp[capacity],
    dp[capacity - weight] + value
)

여기서 capacity를 K부터 weight까지 내림차순으로 순회해야 한다. 오름차순으로 갱신하면 같은 물건으로 방금 바뀐 dp를 다시 읽어 한 물건을 여러 번 넣게 된다. 그것은 0/1 knapsack이 아니라 unbounded knapsack의 상태 전이가 된다.

Java 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

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

        int itemCount = Integer.parseInt(tokenizer.nextToken());
        int maxWeight = Integer.parseInt(tokenizer.nextToken());
        int[] dp = new int[maxWeight + 1];

        for (int item = 0; item < itemCount; item++) {
            tokenizer = new StringTokenizer(reader.readLine());
            int weight = Integer.parseInt(tokenizer.nextToken());
            int value = Integer.parseInt(tokenizer.nextToken());

            for (
                    int capacity = maxWeight;
                    capacity >= weight;
                    capacity--
            ) {
                dp[capacity] = Math.max(
                        dp[capacity],
                        dp[capacity - weight] + value
                );
            }
        }

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

같은 무게나 가치가 있어도 괜찮은 이유

원문에서는 무게 W에 대해 중복된 가치가 생겨도 되는지 고민했다. DP state는 “어떤 가치가 유일한가”를 기록하지 않는다. 현재까지 본 물건 index와 capacity에서 가능한 최대 가치만 필요하다.

무게와 가치가 완전히 같은 물건 두 개도 서로 다른 물건이므로 둘 다 선택할 수 있다. 각 item loop를 한 번씩 거치고 capacity를 내림차순으로 돌기 때문에 같은 index의 물건만 중복 사용하지 않는다.

2차원 정의로 보면 더 분명하다.

dp[item][capacity]
= max(
    dp[item - 1][capacity],
    dp[item - 1][capacity - weight] + value
  )

1차원 구현의 내림차순은 오른쪽 항이 아직 이전 item 단계의 값이도록 보존하는 장치다.

일주일 동안 손대지 못했던 기록

원문에는 대표 knapsack 문제라는 설명을 알고도 약 일주일 동안 손을 대지 못했다고 적혀 있다. 중복된 가치 상태에 대한 의문이 풀리고 점화식을 본 뒤에는 오히려 단순하게 느껴졌다고 남겼다. 이 문제로 당시 단계별 동적 계획법 1 section을 끝냈지만, 몇 달 전 힘겹게 푼 문제를 다시 풀 수 있을지는 의문이라고 솔직하게 적었다.

그 불안은 DP table의 모양을 외우는 대신 상태 문장을 다시 쓰는 이유가 된다. “앞에서 i개 물건만 봤고, 각 물건은 한 번만 쓴다”는 제한이 recurrence와 loop 방향을 결정한다. 구간을 나누는 다른 DP 형태는 백준 11066 파일 합치기에서 비교할 수 있다.

복잡도와 검증 범위

시간 복잡도는 O(NK), 추가 공간은 O(K)다. Java source를 수동 검토하고 capacity 0에 가까운 경우, 선택할 수 없는 무거운 물건, 같은 무게·가치의 별도 물건과 작은 random item set을 모든 subset brute force와 대조한다. 현재 환경에는 실제 JDK가 없어 compile·judge 재제출은 live 반영 전에 별도 확인이 필요하다.