[DP] 0-1 배낭 문제(KnapSack Problem) (Python)

배낭 문제

배낭 문제란 버틸 수 있는 무게가 정해져 있는 배낭이 있고, 일정한 가치와 무게가 있는 짐들을 배낭에 넣을 때, 가치의 합이 최대가 되도록 하는 방법을 찾는 문제이다.

 

배낭 문제는 짐을 쪼갤 수 있는 경우(Fractional)와 없는 경우(0-1)로 구분된다.

쪼갤 수 있는 경우는 무게당 가치가 높은 물건부터 그리디하게 넣으면 $O(N)$만에 해결할 수 있다.

쪼갤 수 없는 경우는 다항 시간에 해결이 불가능하며, 다이나믹 프로그래밍이나 백트래킹과 같은 방법을 적용해야 한다. 

 

이 글에서는 다이나믹 프로그래밍을 이용해 0-1 배낭 문제를 해결해보려고 한다.

 

점화식 세우기

$i$번째 짐까지 고려했을 때, 무게 제한이 $j$인 배낭에 담을 수 있는 최대 가치를 $f(i, j)$라고 하자.

각 짐을 고려할 때 할 수 있는 행동은 아래와 같다.

 

• $i$번째 짐을 담는다: 가치의 총합은 $f(i - 1, j - w_i) + v_i$가 된다. ($w_i, v_i$는 각각 $i$번째 짐의 무게와 가치이다.)
• $i$번째 짐을 담지 않는다: 가치의 총합은 $f(i - 1, j)$와 같다.

 

즉, $f(i, j) = max(f(i - 1, j - w_i) + v_i, f(i - 1, j))$가 성립한다.

 

구현해보기(코드)

dp = [[0] * (k + 1) for _ in range(n + 1)]

for i in range(1, n + 1):
    for j in range(1, k + 1):
        w, v = arr[i - 1]
        dp[i][j] = dp[i - 1][j] # i번째 물건을 담지 않는 경우
        if w <= j: dp[i][j] = max(dp[i][j], dp[i - 1][j - w] + v) # 담는 경우

print(dp[n][k])

 

$arr$은 각 물건들의 무게와 가치가 담긴 리스트이다.

$n$은 $arr$의 크기, $k$는 배낭이 버틸 수 있는 무게이다.

 

코드 최적화: 리스트 차원 줄이기

점화식에서 알 수 있듯이, $f(i, j)$를 구하기 위해서는 $f(i - 1, j - w_i)$와 $f(i - 1, j)$만 알면 된다.

이 사실을 토대로 위 코드의 dp 리스트를 일차원으로 바꿔 공간 복잡도를 줄여보자.

 

dp = [0] * (k + 1)

for w, v in arr:
    for j in range(k, w - 1, -1): # k부터 w까지 역순으로
        # f(i - 1, j)는 이미 dp[j]에 저장되어 있으므로, 다시 계산할 필요가 없다.
        dp[j] = max(dp[j], dp[j - w] + v) # 담는 경우

print(dp[k])

 

중요한 점은 $j$를 1부터 $k$까지 탐색하는 것이 아니라 역순으로 탐색해야 한다는 점이다.

1부터 순서대로 탐색하게 되면 $dp[j - w]$의 값이 $dp[j]$보다 먼저 변경되어 계산 값이 달라진다.

 

각 물건의 개수 제한이 없을 때(Unbounded)

만약 각 물건의 개수가 무제한이라면 어떻게 해결해야 할까?

개수가 무제한이니 더이상 어떤 물건을 담았는 지 아닌 지에 대한 정보는 필요하지 않다.

따라서 개수가 1개일 때에서 $i$와 관련된 부분을 과감히 지워주면 된다.

 

dp = [0] * (k + 1)

for w, v in arr:
    for j in range(w, k + 1):
        dp[j] = max(dp[j], dp[j - w] + v)

print(dp[k])

 

 

관련 문제(BOJ)

• [12865] 평범한 배낭: 가장 기본적인 0-1 배낭 문제
• [1106] 호텔: 개수가 무제한인 배낭 문제
• [7579] 앱: 메모리의 범위가 매우 커 약간의 관점 전환이 필요한 문제