1

valueそれぞれがとを持つアイテムの配列が与えられた場合、最小コストで最小値に到達するために必要なアイテムを決定する最適なアルゴリズムは何ですかcost? 例えば：

Item: Value -> Cost
-------------------
A     20   -> 11
B     7    -> 5
C     1    -> 2

MinValue = 30
naive solution: A + B + C + C + C. Value: 30, Cost 22
best option: A + B + B.            Value: 34, Cost 21

最後の全体的な価値: コストの比率は無関係であることに注意してください (A + Aお金に見合う最高の価値が得られますがA + B + B、最小値に達するより安価なオプションです)。

4

3 に答える 3

8

これがナップザック問題です。(つまり、この問題の決定バージョンは、ナップザック問題の決定バージョンと同じですが、ナップザック問題の最適化バージョンは通常、別の方法で記述されます。) これは NP 困難です (これは、既知のアルゴリズムが存在しないことを意味します)。 「サイズ」の多項式 -- 入力のビット数)。しかし、数値が小さい場合 (たとえば、入力の最大の「値」; コストは問題にならない)、単純な動的計画法のソリューションがあります。

best[v] を (正確に) v の値を取得するための最小コストとします。次に、(すべての best[v] を無限大に初期化して) によって、すべての v の値 best[] を計算できます。

best[0] = 0
best[v] = min_(items i){cost[i] + best[v-value[i]]}

次に、必要な最小値と最大値までの値について best[v] を調べます。それらの最小のものはあなたにコストを与えます。

実際のアイテム (最小コストだけでなく) が必要な場合は、追加のデータを保持するか、best[] の配列を調べてそこから推測することができます。

于 2008-11-27T01:36:34.710 に答える
0

この問題は整数線形計画法として知られています。NP困難です。ただし、例のような小さな問題の場合は、コードを数行すばやく作成して、購入の選択肢の低い組み合わせをすべてブルートフォース攻撃するのは簡単です。

NP-ハードは不可能または高価でさえあるという意味ではありません、それはあなたの問題がより大規模な問題で解決するのが急速に遅くなることを意味します。アイテムが3つしかない場合は、これをわずかマイクロ秒で解決できます。

一般的に最良のアルゴリズムは何かという正確な質問については、教科書全体があります。良いスタートは古き良きウィキペディアです。

于 2009-05-02T13:34:33.813 に答える
-1

編集この回答は、事実上正しくないために編集されています。このアドバイスに従うと、害を及ぼすだけです。

これは実際にはナップサック問題ではありません。これは、一部のコンテナのスペースよりも多くのアイテムをパックできないことを前提としているためです。あなたの場合、あなたはスペースを埋める最も安い組み合わせを見つけたいと思うでしょう、それはオーバーフローが起こるかもしれないという事実を考慮に入れます。

私の解決策は最適かどうかはわかりませんが、かなり近いはずですが、各アイテムの費用便益比を計算し、費用便益が最も高いアイテムを見つけて、なくなるまでこのアイテムで構造を埋めることです。もう1つのアイテムのためのスペース。次に、最も安いアイテムの1つよりも安いコストで利用可能なスロットを埋めることができる他の利用可能なアイテムのいずれかとの組み合わせがあるかどうかをテストし、そのようなソリューションが存在する場合は、その組み合わせを使用します。それ以外の場合は、もう1つ使用します。最も安いアイテムの。

Amenddumこれも実際にはNP完全である可能性がありますが、まだわかりません。とにかく、すべての実用的な目的のために、このバリエーションは素朴な解決策よりもはるかに速いはずです。

于 2009-05-02T13:22:40.860 に答える