ナップサック：状態を何で持つか
品物を1回ずつ選び、容量以内の価値を最大化します。品物数と重さを状態にし、1次元へ圧縮できます。
言語：Python / 計算量：O(NW)、メモリ O(W)
考え方
- dp[w] を重さ上限 w で得られる最大価値と定義します。
- 品物を取らないか、重さ分戻った状態から取るかを比較。
- 1次元の0/1型では重さを大きい方から更新します。
具体例
容量4、品物(重さ2,価値3)を1個。逆順更新なら1回しか使いません。順方向では dp[2] から dp[4] に再利用されてしまいます。
実装
W=4
dp=[0]*(W+1)
for weight,value in [(2,3),(3,4)]:
for w in range(W,weight-1,-1):
dp[w]=max(dp[w],dp[w-weight]+value)
print(dp[W])注意する条件
Wが10^9なら重さDPは無理です。価値総和が小さいなら価値側を状態にする方法を検討します。
確認問題
容量4、品物(2,3),(3,4) の最大価値は？
解答と理由
4
両方だと重さ5で不可。価値4の品物を選びます。
実装課題
N W と N 行の重さ・価値。各品物は1回だけ。総重さ≤W の最大価値。N≤100、W≤10000、重さ≥1、価値≥0。
入力:
2 4
2 3
3 4
出力:
4参考実装
n,W=map(int,input().split())
dp=[0]*(W+1)
for _ in range(n):
w,v=map(int,input().split())
for cap in range(W,w-1,-1):
dp[cap]=max(dp[cap],dp[cap-w]+v)
print(dp[W])