배낭 문제 (Knapsack problem)

소개

배낭 문제는 조합 최적화 카테고리의 대표적인 문제 유형이다.

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

짐을 쪼갤 수 있는 경우는 분할가능 배낭문제(Fractional Knapsack Problem) 이라고 하며, 쪼갤 수 없는 경우는 0-1 배낭문제(0-1 Knapsack Problem) 이라고 한다.

분할가능 배낭문제는 그리디 알고리즘으로 해결이 가능하며, 0-1 배낭문제는 그리디로 해결이 불가능하며, 주로 DP(Dynamic Programming) 로 해결하게 된다.

본 글에서는 0-1 배낭 문제를 DP로 해결하는 방법을 다룬다.

최적화 알고리즘

DP를 통한 최적화 알고리즘의 개발절차는 다음과 같다.

1. 문제의 입력사례에 대해서 최적(optimal)의 해답을 주는 재귀 관계식(recursive property)를 세운다.
2. 상향식으로 최적의 해답을 계산한다.
3. 상향식으로 최적의 해답을 구축한다.

최적의 원칙

최적화 문제를 DP로 풀기 위해서는 최적의 원칙(principle of optimality) 이 성립해야 한다. 최적의 원칙은 다음과 같다.

어떤 문제의 입력사례의 최적해가 그 입력사례를 분할한 부분사례에 대한 최적해를 항상 포함하고 있으면, 그 문제는 최적의 원칙이 성립한다고 한다.

증명

증명을 위해 먼저 $n$개의 짐들 중에서 최적을 이루는 집합을 $A$라고 하자. 이때 $A$가 $n$번째 짐을 포함하는 경우와 포함하지 않는 경우 두 가지로 나누어 생각할 수 있다.

• $A$가 $n$번째 짐을 포함하지 않는 경우 :
  $A$는 처음 $n - 1$개 짐들 중에서 최적을 이루는 부분집합과 같다.

• $A$가 $n$번째 짐을 포함하는 경우 :
  총 무게가 (배낭의 최대 무게 - $n$번째 짐의 무게) 를 초과하지 않는 선에서 처음 $n - 1$개 짐들을 선택하여 얻을 수 있는 최적의 이익에 $n$번째 짐의 이익을 더한 것이 $A$의 이익이다.

즉, 최적의 원칙은 성립한다.

일반화

다음으로 위 내용을 일반화하여 최적의 해답을 계산할 수 있다.

총 무게가 w를 초과할 수 없다는 제약조건 하에서 처음 $i$개 아이템(짐)에서만 선택할 때 얻는 최적의 가치를 $P[i][w]$라고 하면, 다음 식을 얻을 수 있다.

\[P[i][j] = \begin{cases} maximum(P[i - 1][w], p_i + P[i - 1][w-w_i]\quad if\; w_i <= w\\ P[i-1][w]\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\;\, if\; w_i <= w\\\end{cases}\]

배낭의 최대 무게를 $W$라고 했을 때 최대 이익은 $P[n][W]$와 같으며, 이는 이차원 배열을 이용하여 순서대로 값을 구하여 도출이 가능하다. (메모이제이션을 이용하게 된다)

구현

위 식을 파이썬으로 구현해 보면 다음과 같다.

from sys import stdin
input = stdin.readline

n, W = map(int, input().split())        # 아이템(짐)의 개수와 최대 무게
w = list(map(int, input().split()))     # 각 짐의 무게 배열
p = list(map(int, input().split()))     # 각 짐의 가치 배열

dp = [[0 for _ in range(W + 1)] for _ in range(n + 1)] # 메모이제이션 배열
for i in range(1, n + 1):
    for j in range(1, W + 1):
        if w[i - 1] <= j:
            dp[i][j] = max(dp[i - 1][j], p[i - 1] + dp[i - 1][j - w[i - 1]])
        else:
            dp[i][j] = dp[i - 1][j]
print(dp[n][W])

참고도서

Richard E. Neapolitan, “알고리즘 기초”, 도경구 역, 홍릉과학출판사, 2017, p.105, 183