0/1 Knapsack Problem - Dynamic Programming

 얼만큼의 비용과 보상이 정해진 여러개의 물체가 있다고 하자. 특정 용량까지 수용 가능한 마대에 이 물체들을 마대의 최대 수용량을 넘기지 않게 넣어주되, 담겨있는 물체들의 보상의 합이 가능한 경우의 수 중 최대가 되게 하려고 한다. 이 때의 경우를 구하는 것이 본 문제의 핵심이다.

 예를 들면 보석의 수 n이 4로 주어지고, 각각 다음과 같은 조건을 만족한다.

• profit = {1, 2, 5, 6}
• weight = {2, 3, 4, 5}

 보석을 담을 마대의 수용량 m은 8로 주어졌을 때 어떤 보석을 챙겨야 가장 많은 보상을 챙길 수 있을까? 단순히 생각하면 각 보석을 담는 모든 경우의 수 중 한계 수용량을 넘는것을 제외하고 가장 보상의 값이 큰 조합을 찾으면 될 것이다. 하지만 이 경우 2^4 만큼의 연산을 해야하고, 즉 n개의 보석에 대해서 2^n만큼의 연산이 필요해진다는 것이다.

 다행히 본 문제는 반복적으로 최적의 결정을 내려 원하는 값을 도출해낸다는 점에서 DP로의 접근이 타당성을 얻는다. 잠깐 "편집 거리" 문제를 떠올려보자. 해당 문제에서는 어떤 문자열 A를 '편집'해서 문자열 B로 만들기 까지 최소 편집 횟수를 구해야 했다. 문자열의 가장 첫 번째 문자로 B 문자열의 특정 인덱스까지 소요 되는 편집 거리를 각각 따져보고, 두 번째 문자로 넘어가 이전에 얻어낸 결과들을 이용해 다시  최적의 편집 거리를 따져보고, 또 이후 문자들에 대해서도 같은 작업을 시행하며 최종적으로 문자열 A의 문자를 모두 사용하여 B를 만들 수 있는 최적 편집 거리를 얻을 수 있었다. 본 문제도 같은 방식으로, 각 보석들을 차례대로 마대에 넣어보다 최종적으로 최적값을 얻어낸다. DP 테이블을 보면 좀 더 직관적으로 두 문제의 접근 방식이 유사하다는 것을 알 수 있다. 행에는 보석들을 늘어놓고, 열은 마대의 수용량 w를 나타낸다. 아무런 보석을 넣지 않을 때 얻는 보상은 0이므로, 0 번째 행은 전부 0으로 초기화 한다. 마찬가지로 수용량이 0인 마대에는 아무것도 넣을 수 없으므로 0 번째 열 역시 전부 0으로 초기화된다.

	w		0	1	2	3	4	5	6	7	8
p_i	w_i	0	0	0	0	0	0	0	0	0	0
1	2	1	0
2	3	2	0
5	4	3	0
6	5	4	0

 이제 첫 번째 보석을 넣어보도록 하자. 첫 번째 보석의 무게는 2로, 마대의 용량이 2일 때부터 챙길 수 있다.

	w		0	1	2	3	4	5	6	7	8
p_i	w_i	0	0	0	0	0	0	0	0	0	0
1	2	1	0	0	1	1	1	1	1	1	1
2	3	2	0
5	4	3	0
6	5	4	0

 두 번째 보석까지 넣는 경우를 따져본다. 첫 번째 보석과 함께 챙길 수 있는 것은 둘의 무게 합이 5 이기 때문에 마대 수용량이 5 일때 부터이고, 마대 수용량이 2 일때 까지는 첫 번째 보석만 넣을 수 있을 것이다. 그 사이에 있는 3, 4의 경우 두 번째 보석만 넣는것이 더 이득이다.

	w		0	1	2	3	4	5	6	7	8
p_i	w_i	0	0	0	0	0	0	0	0	0	0
1	2	1	0	0	1	1	1	1	1	1	1
2	3	2	0	0	1	2	2	3	3	3	3
5	4	3	0
6	5	4	0

 세 번째 보석까지 넣는다면, 불행히도 세 보석을 모두 넣기엔 마대의 최대 수용량이 모자르다. 대신 두 번째와 세 번째 보석을 함께 챙길 때 무게가 7 이므로, 용량이 7 일때 부터는 두 보석의 보상의 합 7을 (2+5) 얻을 수 있다. 또 첫 번째 보석과 세 번째 보석을 함께 챙긴다면 6의 보상과 6의 무게가 되므로, 용량이 6 일때 최대 보상은 6이 된다. 세 번째 보석만 챙기는 경우 첫 번째, 두 번째를 함께 챙기는 것보다 많은 보상을 얻을 수 있는데, 마대 용량이 4 일때 부터 가능하다. 마대 용량이 4 보다 작은 경우 이미 이전에, 즉 두 번째 보석 까지만 챙긴다고 상정했을 때 결과를 이미 구해놨으므로, DP 표의 5열 역시 모두 채울 수 있다.

	w		0	1	2	3	4	5	6	7	8
p_i	w_i	0	0	0	0	0	0	0	0	0	0
1	2	1	0	0	1	1	1	1	1	1	1
2	3	2	0	0	1	2	2	3	3	3	3
5	4	3	0	0	1	2	5	5	6	7	7
6	5	4	0

 마지막 보석을 넣기 전에, 점화식을 정리하고 가자. DP 표에 대한 점화식은 다음과 같다. i는 보석의 번호, w는 마대의 수용량이다.

$$ dp[i, w] = max(dp[i-1,w], dp[i-1,w-w_i] + p_i) $$

 위 식을 말로 풀이하면 다음과 같다. i 번째 보석까지 용량이 w인 마대에 넣어줄 때 얻을 수 있는 보상의 최대값은, i 번째 보석을 넣지 않고 i-1 번째 보석까지만 상정 했을 때 얻는 보상의 최대값과, i-1 번째 보석 까지만 상정 했을 때 i 번째 보석의 무게 만큼 덜어 그 자리를 i 번째 보석으로 채웠을 때 얻는 보상을 비교하여 더 큰 값이 된다. 쉽게 말하자면 i 번째 보석을 넣냐, 넣지 않냐 중 더 이득인 상태를 고르겠다는 뜻이다. 아무튼 위 식으로 마지막 행 역시 채울 수 있다. 당연하지만 마대 용량이 5가 안될 때 까지는 항상 dp[i, w] = dp[i-1, w]가 될 것이고, 그 후 부터는 조합 가능한 경우 중 최적값으로 표를 채워줄 것이다.

	w		0	1	2	3	4	5	6	7	8
p_i	w_i	0	0	0	0	0	0	0	0	0	0
1	2	1	0	0	1	1	1	1	1	1	1
2	3	2	0	0	1	2	2	3	3	3	3
5	4	3	0	0	1	2	5	5	6	7	7
6	5	4	0	0	1	2	5	6	6	7	8

 위 표를 통해 얻을 수 있는 가장 최적의 보상은 8이라는 것을 알았다. 하지만 어떤 보석을 챙겼는지는 어떻게 알 것인가? 4 번째 보석을 상정했을 때 얻는 보상의 최대값 8은, 3 번째 보석까지만을 상정했을 때는 얻을 수 없음을 표를 통해 확인 가능하다. 따라서 4 번째 보석을 선택했음을 알 수 있다. 4 번째 보석을 선택했으니 3 번째 까지만 상정했을 때는 4 번째 보석의 보상 값을 뺀 2를 얻었을 것이고, 2는 2 번째 보석 까지만 상정 했을 때도 얻을 수 있는 값임이 확인되니 3 번째 보석은 선택하지 않았음을 알 수 있다. 두 번째 보석까지만 상정 했을 때 보상을 2까지 챙겼는데, 첫 번째 보석까지만 상정 했을 때 2까지는 얻지 못한것으로 보아 두 번째 보석도 챙겼음을 알 수 있다. 그럼 첫 번째 보석 까지만 고려 했을 때 0의 보상을 챙겼을 텐데, 보석을 아무것도 챙기지 않는다고 상정했을 때 0이 존재하므로 첫 번째 보석은 챙기지 않았음을 알 수 있다. 결과적으로 최적값에 대한 경우의 수는 [0,1,0,1] 이 되는 것이다.

코드

p = [-1,1,2,5,6]
w = [-1,2,3,4,5]

n,m = 4,8

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

for i in range(1,n+1):
  for j in range(1,m+1):
    dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]]+p[i]) if j >= w[i] else dp[i-1][j]

# dp 테이블 출력
for i in range(n+1):
  print(dp[i])
# 담은 보석 출력
_p = dp[n][m]
for i in range(n,-1,-1):
  try:
    idx = dp[i].index(_p)
  except:
    print(i+1)
    _p = _p - p[i+1]

출력

[0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 1, 1, 1, 1, 1, 1, 1]
[0, 0, 1, 2, 2, 3, 3, 3, 3]
[0, 0, 1, 2, 5, 5, 6, 7, 7]
[0, 0, 1, 2, 5, 6, 6, 7, 8]
4
2