DP D
指定された制限重量以下で価値を最大化する問題
重量を定義域とし、その重量での最大価値を値とするDP
PyPy 166 ms
for j in range(W - weight + 1) の+1を忘れて最大重量の場合を更新し忘れるミスpythondef solve(N, W, WV):
values = [0] * (W + 1)
for i in range(N):
next_values = values[:]
weight, value = WV[i]
for j in range(W - weight + 1):
next_values[j + weight] = max(
values[j + weight],
values[j] + value)
values = next_values
return max(values)"Engineer's way of creating knowledge" the English version of my book is now available on [Engineer's way of creating knowledge]
(C)NISHIO Hirokazu / Converted from [Scrapbox] at [Edit]