1. 문제

최대 무게 K까지 담을 수 있는 배낭에 무게 W[i], 가치 V[i]인 N개의 물건 중 가능한 많은 물건을 담아 가치의 총합을 최대로 하고자 할 때, 그 가치 총합의 최댓값을 구하는 문제.

2. 풀이

배낭에 담을 수 있는 최대 무게 K가 아주 크지 않다면 간단한 다이나믹 프로그래밍으로 풀 수 있다.

dp[i][j]: 배낭에 i번째 물건을 담아 무게가 j가 되었을 때 배낭에 담긴 물건들의 가치 총합의 최댓값

위와 같이 dp 배열을 정의하면 다음 점화식을 세울 수 있다.

dp[i][j] = max( dp[i-1][j], dp[i-1][j-W[i]] + V[i] )

dp[i][j] 값을 채울 때 생각할 수 있는 경우의 수로 i번째 물건을 배낭에 담지 않는 경우와 i번째 물건을 배낭에 담는 경우를 비교할 수 있다. 이 경우 i번째 물건을 배낭에 담지 않는 대신 i-1번째 물건까지 배낭에 담아 무게를 j로 만들었을 때의 최댓값(=dp[i-1][j])과 i-1번째 물건까지 배낭에 담아 무게를 j-W[i]로 만들었을 때의 최댓값에 V[i]를 더한 값(=dp[i-1][j-W[i]] + V[i])을 비교하여 dp[i][j] 값을 구할 수 있다.

3. 구현

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

def knapsack(N, K, W, V):
    dp = [[0 for _ in range(K+1)] for _ in range(N)]
    for j in range(W[0], K+1):
        dp[0][j] = V[0]

    for i in range(1, N):
        for j in range(1, K+1):
            if j-W[i] < 0:
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = max( dp[i-1][j], dp[i-1][j-W[i]] + V[i] ) 

    return dp[N-1][K]

N, K = list(map(int, input().split()))
W, V = zip(*[list(map(int, input().split())) for _ in range(N)])
print(knapsack(N, K, W, V))

4. 한계

위 코드는 배낭에 담을 수 있는 최대 무게 K에 시간복잡도가 의존하는(O(NK)) 알고리즘으로, 만약 배낭에 담을 수 있는 최대 무게 K가 터무니없이 큰 값이 입력으로 들어온다면 그만큼 오랜 시간이 걸리게 된다. K가 너무 크면, 차라리 N개의 물건을 배낭에 넣는 모든 경우의 수(=\(2^N\))를 검토해보는 게 문제를 푸는 데 더 빠른 경우가 있을 수 있다. 이처럼 배낭에 담을 수 있는 최대 무게가 터무니없이 큰 배낭문제는 지수시간 알고리즘으로 푸는 게 차라리 더 빠를 수 있으며, 이 문제를 물건 개수 N에 관한 선형시간 안에 해결하는 알고리즘은 아직 알려지지 않았다. 즉, 배낭에 담을 수 있는 최대 무게가 터무니없이 큰 배낭문제는 NP문제에 해당한다.