私はナップザック問題の 2 つのバリエーションを知っています。0-1 のバージョンには分数の重みを含めることはできません (取るかそのままにするか)。たとえば、2 番目に最適な選択肢の半分を取ることはできません。もう 1 つのバージョンは逆で、小数の項目が許可されます。この小さな違いは非常に重要であり、部分バージョンに有利に働きます。
分数バージョンは貪欲なアルゴリズムを介して解決できます。最も価値のある「単価」を持つアイテムを、できるだけ多く取ることができます。トラックがいっぱいになるまで繰り返します。
0-1 バージョンは、単純な貪欲なアルゴリズムでは解決できないため、少し難しくなります。例として、トラックが 800 ポンドを運ぶことができるとします。から選ぶことができます
- 1 テーブル 500 ポンド、価値が $1000 のテーブル (単価 $2/ポンド)
- 1 ベンチ : 重量 - 701 ポンド : 価値 - $1577.25 : 単位 $2.25/ポンド
- 3 本棚 : 重量 - 100 ポンド : 価値 - $200 : 単位 $2/ポンド
貪欲なアルゴリズムは、合計 1577.25 ドルのベンチを獲得します。
最適な値は、本棚 3 台とテーブル = $1600 です。
上記が部分的なナップザック バージョンである場合、合計 1775.25 ドルのベンチと 99 ポンドのテーブル/本棚が必要になります。
0-1 の場合、動的計画法などを使用してすべてのソリューションを調べる必要があります。