このタイプのアルゴリズムを検索し、多くのものを赤くしましたが、探しているものを正確に見つけることができませんでした。
だから、私は買い物に行くつもりで、私は x のお金を持っています。私のトラックは最大 y の重量を運ぶことができ、各アイテムには重量と価格のボーナスクレジットがあります。出力は、選択したアイテムの総重量がトラックの容量と私が費やさなければならないお金を超えないように、取得できる最大のボーナスクレジットを与える必要があります!
アルゴリズムの名前を知っていますか？どのように進めればよいですか？私はCでそれをしなければなりません！
ありがとう ！！
私はナップザック問題の 2 つのバリエーションを知っています。0-1 のバージョンには分数の重みを含めることはできません (取るかそのままにするか)。たとえば、2 番目に最適な選択肢の半分を取ることはできません。もう 1 つのバージョンは逆で、小数の項目が許可されます。この小さな違いは非常に重要であり、部分バージョンに有利に働きます。
分数バージョンは貪欲なアルゴリズムを介して解決できます。最も価値のある「単価」を持つアイテムを、できるだけ多く取ることができます。トラックがいっぱいになるまで繰り返します。
0-1 バージョンは、単純な貪欲なアルゴリズムでは解決できないため、少し難しくなります。例として、トラックが 800 ポンドを運ぶことができるとします。から選ぶことができます
貪欲なアルゴリズムは、合計 1577.25 ドルのベンチを獲得します。
最適な値は、本棚 3 台とテーブル = $1600 です。
上記が部分的なナップザック バージョンである場合、合計 1775.25 ドルのベンチと 99 ポンドのテーブル/本棚が必要になります。
0-1 の場合、動的計画法などを使用してすべてのソリューションを調べる必要があります。
何を試しましたか？
これらのタイプの問題は、通常、最適化または制約充足のカテゴリに分類されます。
問題の関数式を書いてみて、単純な微積分法またはシンプレックス法で解決できるかどうかを確認してください。
商品の重量と商品の価格は制約です。ボーナスクレジットが目的です。したがって、多次元のナップザック問題 (1 つの目的と 2 つの制約) があります。よく知られている動的プログラミング ソリューションのナップサックは一般化されますが、複雑さは制約の数に応じて指数関数的に増大します。