냅색DP(knapsack DP)

위처럼 작은 상자들이 저마다 무게와 가치를 가지고 있을 때,

15Kg 등 가방의 무게수납제한 하에서 어떤 박스들을 선택해서 가방에 넣어야 가장 많은 돈이 될까?

라는 형식의 문제를 냅색 문제라고 한다.

 

이때 같은 상자를 중복해서 여러 번 넣을 수 있으면 unbounded knapsack problem(UKP)라고 하고,

단 한번씩만 넣을 수 있으면 0-1 knapsack problem이라고 한다. 

(위 두가지 버전 사이에 K번 넣을 수 있는 버전으로 bounded knapsack problem도 있긴 함)

 

아래는 관련 문제 리스트

https://www.acmicpc.net/problemset?sort=ac_desc&algo=148 

문제 - 1 페이지

 

 

0-1 냅색

일반적으로는 0-1 냅색 버전이 가장 흔하다.

 

이문제는 NP완전에 해당하는 문제로 브루프포스로 모든 경우의 수를 해보는 것 이외에 더 효율적인 방법은 없는 것으로 알려져 있다.

모든 경우의 수를 해보려면 상자의 개수가 n개일 때 $O(2^n)$의 복잡도를 가진다(0-1 냅색의 경우)

 

n의 개수가 대략 20 이하일 때는 브루트 포스로 풀수 있다. 이 문제를 통해 체크해보자.

내 브루트포스 답안은 다음과 같다.

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<(int)(n);i++)
 
int32_t main()
{
    int N; scanf("%d", &N);  // 사람수 <=20
    int L[21] = {}; REP(i, N)scanf("%d", L + i);  // 체력 <= 100
    int J[21] = {}; REP(i, N)scanf("%d", J + i);  // 기쁨 <= 100
    int ans = 0;
    for (int i = 0; i < (1 << N); i++) {
        int jsum = 0;
        int lsum = 0;
        for (int j = 0; j < N; j++) {
            if (i & (1 << j)) jsum += J[j], lsum += L[j];
        }
        if (lsum < 100) ans = max(ans, jsum);
    }
    printf("%d\n", ans);
    return 0;
}
 

 

n의 개수가 20을 넘어갈 때는 DP로 푸는 게 기본이고, 이 문제가 기본에 해당한다고 볼 수 있다.

아래 영상에서 다루었다.

https://youtu.be/frlRE7 bRIDo

내 경우, 위 풀이에도 나와있지만, 대체로 iterative DP보다 recursive DP(DFS + memoization)가 훨씬 생각하기 수월한 경우가 많았다.

 

UKP

상자를 반복해서 사용 가능할 경우 UKP문제가 된다. 이 문제가 기본에 해당한다고 볼 수 있다.

 

이 문제는 recursive DP로는 시간 초과가 났고, iterative DP 버전도 배열 크기 줄이기 신공을 써야 통과했다.

 

경우에 따라 UKP문제를 0-1 냅색으로 변환해서 시간 복잡도를 낮출 수 있다. 이 문제를 참조하자.