냅색 문제

남는 시간에 https://www.acmicpc.net/step 에 있는 알고리즘 문제들을 처음부터 쭉 풀어보고 있다. 오늘 작성할 문제는 dp의 대표적인 문제인 배낭 문제(knapsack problem) 이다.

Problem

백준 평범한 가방

가방에 담을 수 있는 무게의 최대값 k와 물건의 총 개수 n, 그리고 각 물건의 무게와 가치가 주어진다. 가방안에 무게가 k가 되지 않도록 물건을 넣을때 가방에 담을 수 있는 가치 합의 최대값을 구한다.

Solution

Idea

X축을 무게 Y축을 가치로 하는 XY평면에 점을찍어 Y최댓값을 찾는다. 새로운 무게를 추가할때는 그래프에 표시된 모든점에 (x_old+x_new, y_old+y_new)를 계산하고 더해진 X에 Y값이 이미 존재하는 경우 Y를 더 큰 값으로 업데이트 한다.

Code

import sys
from collections import defaultdict

input_ = sys.stdin.readline

n, k = map(int, input_().split())
items = [tuple(map(int, input_().split())) for _ in range(n)]
values = defaultdict(int)
values[0] = 0

for cur_weight, cur_value in items:
    keys = sorted(values.keys(), reverse=True)
    for last_weight in keys:
        added_weight = last_weight+cur_weight
        if added_weight > k:
            continue
        values[added_weight] = max(values[added_weight], values[last_weight]+cur_value)

print(max(values.values()))

What I missed

처음에는 12번 라인이 무게가 큰 순서대로 정렬하는 대신 list(values.keys())였다. 이에 따라 17번 라인에서 새 무게에 대한 가치를 업데이트 할 때 업데이트 한 내용을 다시 읽어 더하는 문제가 있었다.

Counterexample:

4 10
5 3
5 5
2 2
3 2
wrong output   : 10
expected output: 9

위와 같은 입력이 주어지는 경우 values[5] = 5로 업데이트 된 채 values[10]을 계산해 최대 가치가 10으로 나온다. 이에 매번 키를 무게가 큰 순서대로 정렬해 한 iteration에서 자신이 업데이트 한 값을 다시 읽는 것을 막아야했다.

배열을 선언하는 대신 딕셔너리를 사용한 것은 정확히 len(keys)만큼만 연산을 진행하려 한것인데, 매번 정렬을 하게되어 좋은 코드가 아니게 되었다.

Time Complexity (Big-O)

딕셔너리 key길이의 최대값이 k이므로 kn의 복잡도를 가진다. 만약 k가 무한하다면 $n*2^n$의 복잡도를 가진다.(ex: 입력이 $a^0, a^1, a^2, …, a^{n-1}$) 으로 들어옴)

Other Solutions

Big-O에서 시간 복잡도는 같다. 배열을 순차적으로 업데이트 해서 매번 불필요한 정렬이 사라진다.

Traditional Knapsack

i를 가방의 최대 허용 무게, j를 탐색한 아이탬의 인덱스로 표현했을 때 점화식은 다음과 같다. $dp[i][j] = max(dp[i][j-1], dp[i-w_j][j-1]+v_j)$

Code

import sys

input_ = sys.stdin.readline

n, k = map(int, input_().split())
items = [tuple(map(int, input_().split())) for _ in range(n)]

dp = [[0]*(n+1) for _ in range(k+1)]
for i in range(1, k+1):
    for j in range(1, n+1):
        weight = items[j-1][0]
        value = items[j-1][1]
        if weight > i:
            dp[i][j] = dp[i][j-1]
        else:
            dp[i][j] = max(dp[i][j-1], dp[i-weight][j-1]+value)

print(dp[k][n])

불필요한 정렬이 사라지고 big-o 복잡도가 같아 다음 코드가 더 빠를 것이라 생각했는데 백준 테스트 케이스 실행 시간이 632ms(PyPy3)가 걸렸다. 원래 코드의 실행 시간이 328ms로 두배 가까이 느리다.

위 코드는 언제나 kn을 모두 탐색하지만 내 코드는 탐색할 keys의 길이가 worst case에서 k여서 klog(k)의 정렬 시간을 포함해도 평균 복잡도가 현재 주어진 테스트 케이스에 대해서는 나은 것 같다.

Best Solution

일차원 배열을 사용해 공간복잡도를 줄인 방법이다. 이차원 배열을 사용하는 냅색문제에서 사실 중요한것은 배낭 크기에대한 가치의 최댓값 뿐이다. 이에 i,j로 표현하던 배열을 i번째 아이템까지 탐색하면서 최댓값을 업데이트하는 방식으로 바꿀 수 있다. 점화식은 다음과 같다.

$dp[i] = max(dp[i], dp[i-w_j]+v_j)$

코드에서는 배열을 뒤에서 부터 업데이트해 자신이 업데이트 한 값을 다시 업데이트 하는 것을 막는다.

Code

import sys

input_ = sys.stdin.readline

n, k = map(int, input_().split())
items = [tuple(map(int, input_().split())) for _ in range(n)]

dp = [0]*(k+1)
for weight, value in items:
    for i in range(k, weight-1, -1):
        dp[i] = max(dp[i-weight]+value, dp[i])

print(dp[k])

백준 테스트 케이스에 대해 실행 시간이 160ms로 가장 빠르다.