배낭 문제
보석 N개가 각각 (무게, 가치)로 주어진다. 최대 W의 무게를 견딜 수 있는 배낭에 보석을 넣는다고 가정하였을 때의 최대 가치를 구하자.
dp 문제의 대표 유형 중 하나인 배낭 문제이다. 보석의 수를 N, 배낭이 견딜 수 있는 무게를 W라고 했을 때 dp[N][W]를 구해보자. 이때 dp[n][w]의 의미는 다음과 같다.
- w: 가방이 견딜 수 있는 무게
- n: n번째 보석까지만을 고려
- dp[n][w]: 가방이 견디는 무게, 고려하는 보석이 w, n일 때 얻을 수 있는 최대 가치
점화식은 매우 간단하다. n번째 보석을 넣는 경우 / 넣지 않는 경우 두 가지만 고려하면 된다. 이 문제가 0-1 KnapSack인 이유이다. 이 때, 보석을 넣지 않는 경우는 n번째 보석이 가방이 허용하는 무게보다 무거운 경우이다. 이를 고려하여 코드를 짜면 다음과 같다.
N, W = map(int, input().split())
value, weight = [0], [0]
for _ in range(N):
w, v = map(int, input().split())
value.append(v)
weight.append(w)
dp = [[0 for _ in range(W+1)] for _ in range(N+1)]
for i in range(1, N+1):
for w in range(1, W+1): # w: 현재 가방이 허용하는 최대 무게
if weight[i] > w: # 현재 보석의 무게가 가방이 허용하는 무게보다 큰 경우 패스
dp[i][w] = dp[i-1][w]
else:
# i번째 보석을 가방에 넣는다고 가정
# 남은 가방의 무게는 w-weight[i]
# i번째 보석을 포함하지 않고 w-weight[i]만큼의 무게를 허용하는 가방 value의 최대치를 더하자.
dp[i][w] = max(dp[i-1][w], value[i] + dp[i-1][w-weight[i]])
위의 코드로 12865번 평범한 배낭 문제를 해결할 수 있다.
1차원 배열 최적화
사실 2차원 배열을 쓸 필요도 없다. dp[i]를 구하기 위해 dp[i-1]의 정보만을 사용하는데, 이 경우 1차원 배열만으로도 문제를 해결할 수 있다.
1차원 배열로 해결하는 코드는 다음과 같다.
dp = [0 for i in range(W+1)] # 1차원 배열로 변경 -> 최대 허용 무게만을 인덱스로 사용
for i in range(1, N+1):
for w in range(W, weight[i]-1, -1): # W부터 현재 무게까지 역순으로 순회
## 항상 가방보다 큰 보석만을 순회하므로 아래 코드는 필요 없음
#if weight[i] > w:
# dp[i][w] = dp[i-1][w]
# 우변에 있는 dp[w]가 이전 순회의 dp[i][w]이므로 현재 순회에서 dp[i-1][w]와 동일함
dp[w] = max(dp[w], value[i] + dp[w-weight[i]])
코드가 훨씬 간결해졌다. 1차원 dp 배열을 여러 번 순회하므로, 이전 회차에 순회한 dp[w]가 2차원 배열에서의 dp[i-1][w]의 역할을 수행할 수 있다.
핵심은 1차원 배열의 경우 dp[w]의 순회를 역순으로 진행한다는 점이다. 만약 역순으로 진행하지 않는다면 다음과 같은 불상사가 발생한다.
(w, v) = (3, 3)인 보석 한 개만 존재하고, 1부터 정방향으로 진행한다고 고려해보자.
- dp[0], dp[1], dp[2]는 모두 0이다.
- dp[3] = 3(value) + dp[0] = 3
- dp[4], dp[5] = 3
- dp[6] = 3 + dp[3] = 6
dp[5]까지는 잘 가다가, dp[6]에서 문제가 발생한다. dp[6] = 3+dp[3]인데, dp[3]에서 이미 보석을 사용했다. 즉, 이 식에서 구한 dp[6]은 같은 보석을 두 번 사용한 것이다.
따라서 보석 중복 사용 문제를 방지하기 위해 역순으로 순회하여야 한다.
중복을 허용하는 배낭 문제
이 경우, 이미 위에 해결책이 나와 있다! 1차원 배열을 활용하여, 정방향으로 순회한다면 중복을 포함한 배낭 문제를 해결할 수 있다.
