ナップサック問題の内訳

Question

競技プログラミングで頻出の「ナップサック問題」について質問です。

動的計画法という考え方を用いて価値の最大値を求めることは理解しました。

そこで、気がついたのですが、「何と何と何をそれぞれ何個ずつ組み合わせて」価値が最大になったというところを表すにはどのようなコードを追加すればよろしいでしょうか。

初歩的な質問ですみませんが、教えていただけますと幸いです。

⇩価値の最大値を表示するコード

#n：物の数
#W：ナップサックの容量
#v：物の価値
#w：物の重さ

n,W=map(int,input().split())
dp=[0 for j in range(W+1)]
for i in range(n):
    v,w=map(int,input().split())

    for j in range(w,W+1):
        dp[j]=max(dp[j],dp[j-w]+v)

print(dp[W])

Comments

[melian]

ナップサック問題の解法 for Python
https://qiita.com/kzy83/items/64be4f5f1eaf08917f24

[actorbug]

意外と解説がない！動的計画法で得た最適解を「復元」する一般的な方法
https://qiita.com/drken/items/0c7bab0384438f285f93

Answer 1

汎用的な方法については、以下のページが詳しいので、そちらを参照していただければよいでしょう。
意外と解説がない！動的計画法で得た最適解を「復元」する一般的な方法

品物の使用数に制限のない今回のケースに限れば、1次元配列を逆順にたどることで組み合わせを再現することも可能です。

n,W=map(int,input().split())
dp=[0 for j in range(W+1)]
v=[0]*n
w=[0]*n
for i in range(n):
    v[i],w[i]=map(int,input().split())

    for j in range(w[i],W+1):
        dp[j]=max(dp[j],dp[j-w[i]]+v[i])

print(dp[W])

c=[0]*n
for i in range(n-1, -1, -1):
    while W >= w[i] and dp[W]==dp[W-w[i]]+v[i]:
        c[i] += 1
        W -= w[i]
for i in range(n):
    if c[i]:
        print(f"({v[i]},{w[i]}) x {c[i]}")

最初のリンクの「方法 1： 素朴なやり方」に従っていると考えると分かりやすいでしょうか。

i番目の品物を選択して、重さWに到達したとすると、while W >= w[i] and dp[W]==dp[W-w[i]]+v[i]:の条件が成り立つはずです。
(条件が成り立つ = dp[j]=max(dp[j],dp[j-w[i]]+v[i])で右が選ばれた = i番目の品物が選択された)

そのようなルートをたどっていけば、最終的にdp[W]が0となるスタート地点まで戻れます。
たどったルートから、荷物の組み合わせが分かるという原理です。

なお、品物を選択する順番を変えても最終的な価値は変わらないので、毎回すべての品物を確認せずとも、品物を順番に確認すればよいことが分かります。