배낭 문제에서 상태를 정하는 축은 남은 용량 하나다. 지금까지 무엇을 담았는지는 앞으로의 선택에 영향을 주지 않는다. 같은 물건을 다시 담을 수 있는 형태라 더 그렇다.
그래서 배열 하나면 된다.
t = 5
v = [10, 20, 30, 50]
w = [ 5, 4, 2, 3]
dp = [0] * (t + 1)
for cur_t in range(1, t + 1):
for j in range(len(v)):
if cur_t >= w[j]:
dp[cur_t] = max(dp[cur_t], dp[cur_t - w[j]] + v[j])
dp[i] 는 용량이 i 일 때의 최대 값이다.
바깥이 용량이고 안쪽이 물건이다. 용량 i 를 채우는 마지막 물건이 j 였다고 하면, 그 앞은 용량 i - w[j] 짜리 문제이고 답은 이미 dp[i - w[j]] 에 있다. 물건을 다 훑어보고 가장 큰 걸 남긴다.
dp = [0, 0, 30, 50, 60, 80]
dp[2] 가 30인 건 무게 2짜리 하나, dp[5] 가 80인 건 2와 3을 담은 것이다.
dp[i - w[j]] 를 읽을 때 그 값이 이번 라운드에 이미 갱신됐을 수 있는데, 여기서는 그게 맞다. 같은 물건을 여러 번 담을 수 있으므로 이미 그 물건을 쓴 상태에서 또 써도 된다.
2차원으로 만들려다 만 것
물건 축을 따로 두고 표로 만들어봤다.
dp = [[0] * len(v) for _ in range(t + 1)]
for j in range(len(v)):
for cur_t in range(1, t + 1):
if cur_t >= w[j]:
dp[cur_t][j] = max(max(dp[cur_t - w[j]]) + v[j], max(dp[cur_t]))
print(dp[t][len(v) - 1])
max(dp[cur_t - w[j]]) 처럼 행 전체에 max 를 씌우고 있다. 물건 축을 만들어놓고 결국 그 축을 무시하고 행에서 제일 큰 값을 쓰는 것이라, 축을 나눈 의미가 없어졌다.
읽기도 어려워졌다. 1차원 쪽은 dp[i - w[j]] + v[j] 가 무슨 뜻인지 바로 보이는데 이쪽은 max 가 두 겹이라 뭘 비교하는 건지 한참 봐야 한다.
물건을 한 번씩만 담을 수 있는 형태였다면 물건 축이 실제로 필요하다. 이번 문제는 그게 아니라서 1차원으로 충분했다.
값의 차이 보기
용량을 하나씩 늘릴 때 값이 얼마나 오르는지도 찍어봤다.
for i in range(t, 0, -1):
print(dp[i] - dp[i - 1])
20 10 20 30 0
용량이 4에서 5로 갈 때 20이 오르고, 2에서 3으로 갈 때 30이 오른다. 마지막 0은 용량 1에서는 담을 수 있는 게 없다는 뜻이다.
증가폭이 들쭉날쭉하다. 용량을 늘렸다고 값이 그만큼 꾸준히 오르지 않는다. 무게가 딱 맞아떨어지는 지점에서 뛴다.