基本的なプログラミングの原則を独学で学んでいますが、動的プログラミングの問題で行き詰まっています。悪名高いナップザック問題を見てみましょう:
それぞれが重みと値を持つ一連のアイテムを指定して、コレクションに含める各アイテムの数を決定し、合計重量が指定された制限以下になり、合計値ができるだけ大きくなるようにします。
重み制限を 10 に設定し、2 つのリストを与えましょう: weights = [2,4,7] と values = [8,4,9] (これらは作成したばかりです)。制約が与えられた場合に最大値を与えるコードを書くことができますが、それは問題ではありません。しかし、実際に使用した値を知りたい場合はどうでしょうか? 合計値ではなく、個々の値です。したがって、この例では、最大値は重みが 2 と 7 のオブジェクトで、合計値は 8 + 9 = 17 になります。ただし、答えを「17」と読みたくないので、リストの出力が必要です。のように: (8, 9). この問題は簡単かもしれませんが、私が取り組んでいる問題は、はるかに大きく、繰り返し番号を持つリストを使用しています (たとえば、複数のオブジェクトの値は 8 です)。
何か思いつく人がいたら教えてください。いつものように、コミュニティに多くの愛と感謝を。