Algorithms/DP Applications

2.16.1 Knapsack

개념

무게 제한 안에서 물건 가치의 합을 최대화하는 문제입니다. 무게당 가치가 높은 물건부터 고르는 방식은 물건을 쪼갤 수 없는 경우 최적해를 보장하지 않습니다.

예를 들어 무게 한도가 44이고 물건의 (무게, 가치)가 (3,5),(2,3),(2,3)(3,5),(2,3),(2,3)이라면, 무게당 가치가 가장 큰 (3,5)(3,5)를 먼저 골랐을 때 가치는 55입니다. 반면 무게 22인 두 물건을 고르면 가치가 66입니다. 각 물건을 고르는 경우와 고르지 않는 경우를 함께 비교해야 합니다.

상태와 점화식

DcD_c를 무게 한도가 cc일 때 얻을 수 있는 최대 가치로 정의합니다. 무게 ww, 가치 vv인 물건을 넣는다면 이전 무게 한도 c−wc-w에서 얻은 가치에 vv를 더합니다.

Dc←max⁡(Dc,Dc−w+v).D_c\gets\max(D_c,D_{c-w}+v).

아무것도 고르지 않는 경우의 가치는 00이므로 초기값은 모두 00입니다. 정확히 정해진 무게를 채워야 한다면, 물건을 골라 만들 수 없는 무게는 따로 표시해야 합니다.

반복 방향

0/1 배낭에서는 각 물건을 한 번만 고릅니다. 한 물건을 처리할 때 용량을 큰 쪽부터 줄이면 아직 그 물건을 사용하지 않은 이전 상태를 참조합니다.

무제한 배낭에서는 같은 종류를 여러 개 고를 수 있습니다. 용량을 작은 쪽부터 늘리면 현재 물건을 사용한 상태를 다시 참조할 수 있습니다. 무게는 양수여야 합니다.

무게 22, 가치 33인 물건 하나와 한도 44를 생각하면 반복 방향의 차이가 드러납니다.

  • 큰 한도부터 계산하면 한도 44를 처리할 때 한도 22에는 아직 이 물건이 반영되지 않았습니다. 따라서 한도 44의 최대 가치는 0+3=30+3=3입니다. 물건 하나만 사용한 결과입니다.
  • 작은 한도부터 계산하면 먼저 한도 22의 가치가 33이 됩니다. 이후 한도 44에서는 그 값에 다시 33을 더해 66이 됩니다. 같은 종류를 두 개 사용한 결과입니다.

따라서 각 물건을 한 번만 고르는 0/1 배낭은 큰 한도부터, 같은 종류를 반복해서 고르는 무제한 배낭은 작은 한도부터 계산합니다. 실행 가능성은 물건 수뿐 아니라 한도 크기에도 좌우됩니다. 종류가 100100개이고 한도가 10001000이면 약 1010만 개의 조합을 확인하지만, 한도가 10000001000000이면 약 11억 개로 늘어납니다.

복잡도

물건 종류를 NN, 무게 한도를 WW라고 합니다.

연산시간복잡도공간복잡도
0/1 배낭·무제한 배낭O(NW)O(NW)DP 표 O(W)O(W)

예제

문제

물건들의 무게와 가치가 주어진다. 무게의 합이 WW 이하가 되도록 물건을 고른다. 각 물건을 한 번만 고를 때와 각 종류를 여러 번 고를 때 얻을 수 있는 최대 가치를 각각 구하여라.

입력

첫째 줄에 물건 종류 수 NN과 담을 수 있는 최대 무게 WW가 공백을 사이에 두고 주어진다. 1≤N≤301\le N\le30; 1≤W≤1001\le W\le100이다.

다음 NN개 줄에 각 종류의 무게 ww와 가치 vv가 공백을 사이에 두고 주어진다. 1≤w,v≤1001\le w,v\le100이다.

출력

첫째 줄에 각 물건을 한 번만 고를 때의 최대 가치를 출력한다. 둘째 줄에 각 종류를 여러 번 고를 때의 최대 가치를 출력한다.

예제 입력

2 6
2 3
3 5

예제 출력

8
10

예제 코드

C++20

#include <iostream>
#include <algorithm>

using namespace std;

int dp[101], un[101];

int main() {
    int n, limit, i, c, w, v;

    cin >> n >> limit;
    for (i = 0; i < n; ++i) {
        cin >> w >> v;
        // 큰 용량부터 갱신하여 같은 물건의 중복 선택 방지
        for (c = limit; c >= w; --c) {
            dp[c] = max(dp[c], dp[c - w] + v);
        }
        // 작은 용량부터 갱신하여 같은 종류를 다시 선택
        for (c = w; c <= limit; ++c) {
            un[c] = max(un[c], un[c - w] + v);
        }
    }
    cout << dp[limit] << '\n' << un[limit] << '\n';
}