dp[t] 는 최대 값이 얼마인지만 알려준다. 무엇을 담아서 그 값이 나왔는지는 안 남는다.
값과 같은 인덱스에 리스트를 하나 더 두고 같이 갱신해봤다.
dp = [0] * (t + 1)
li = [[]] * (t + 1)
for i in range(1, t + 1):
for j in range(len(v)):
if w[j] <= i:
dp[i] = max(dp[i], dp[i - w[j]] + v[j])
li[i] = li[i - w[j]] + [w[j]]
dp[i] 를 dp[i - w[j]] 에서 끌어왔으니, 목록도 li[i - w[j]] 에 이번 물건을 붙이면 된다는 생각이다.
돌려보면 [2, 3] 이 나온다. 무게 합이 5고 값이 80이라 맞는 답이다.
그런데 조건 안에 있어야 한다
dp[i] 는 max 로 갱신된다. 즉 이번 j 가 더 나은 경우에만 값이 바뀐다. 그런데 li[i] 는 if w[j] <= i 만 통과하면 무조건 덮인다.
값은 최선을 유지하는데 목록은 마지막으로 들어간 물건 기준으로 덮이는 것이다. 둘이 어긋날 수 있다.
위 입력에서는 맞게 나왔다. 마지막에 시도한 물건이 마침 최선의 조합에 속해 있었기 때문이다.
다른 값을 넣어보면 갈라진다.
t = 4
w = [2, 4, 5, 5]
v = [16, 13, 21, 28]
값은 32가 나온다. 무게 2짜리를 두 번 담은 것이다. 그런데 목록에는 [4] 만 들어 있고, 그 물건의 값은 13이다.
갱신을 조건 안으로
같은 notebook의 다른 문제에서는 이렇게 되어 있다.
for i in range(sack + 1):
for j in range(len(data)):
if i >= data[j][0]:
temp = dp[i - data[j][0]] + data[j][1]
if temp > dp[i]:
dp[i] = temp
jewel[i] = jewel[i - data[j][0]] + [data[j][0]]
max 를 쓰지 않고 temp 에 담아 비교한 뒤, 더 클 때만 값과 목록을 같이 바꾼다. 둘이 같은 if 안에 있으므로 어긋날 수가 없다.
max 를 쓰면 갱신이 일어났는지 알 수 없다. 값 옆에 뭔가를 같이 끌고 가야 하면 max 대신 비교문을 직접 쓰는 편이 낫다.
리스트로 초기화할 때
li = [[]] * (t + 1)
[[]] * n 은 같은 리스트 하나를 n 번 가리킨다. 한 칸에 append 를 하면 전부 바뀐다.
여기서는 li[i - w[j]] + [w[j]] 로 새 리스트를 만들어 대입하기 때문에 문제가 안 생긴다. li[i].append(...) 였다면 전부 뭉개졌다.