回答編集履歴
1
リンクと解説追加
test
CHANGED
|
@@ -1,3 +1,6 @@
|
|
|
1
|
+
汎用的な方法については、以下のページが詳しいので、そちらを参照していただければよいでしょう。
|
|
2
|
+
[意外と解説がない！動的計画法で得た最適解を「復元」する一般的な方法](https://qiita.com/drken/items/0c7bab0384438f285f93)
|
|
3
|
+
|
|
1
4
|
品物の使用数に制限のない今回のケースに限れば、1次元配列を逆順にたどることで組み合わせを再現することも可能です。
|
|
2
5
|
|
|
3
6
|
```python
|
|
@@ -22,3 +25,13 @@
|
|
|
22
25
|
if c[i]:
|
|
23
26
|
print(f"({v[i]},{w[i]}) x {c[i]}")
|
|
24
27
|
```
|
|
28
|
+
|
|
29
|
+
最初のリンクの「[方法 1： 素朴なやり方](https://qiita.com/drken/items/0c7bab0384438f285f93#%E6%96%B9%E6%B3%95-1-%E7%B4%A0%E6%9C%B4%E3%81%AA%E3%82%84%E3%82%8A%E6%96%B9)」に従っていると考えると分かりやすいでしょうか。
|
|
30
|
+
|
|
31
|
+
`i`番目の品物を選択して、重さ`W`に到達したとすると、`while W >= w[i] and dp[W]==dp[W-w[i]]+v[i]:`の条件が成り立つはずです。
|
|
32
|
+
(条件が成り立つ = `dp[j]=max(dp[j],dp[j-w[i]]+v[i])`で右が選ばれた = `i`番目の品物が選択された)
|
|
33
|
+
|
|
34
|
+
そのようなルートをたどっていけば、最終的に`dp[W]`が0となるスタート地点まで戻れます。
|
|
35
|
+
たどったルートから、荷物の組み合わせが分かるという原理です。
|
|
36
|
+
|
|
37
|
+
なお、品物を選択する順番を変えても最終的な価値は変わらないので、毎回すべての品物を確認せずとも、品物を順番に確認すればよいことが分かります。
|