パッキングアルゴリズム＆＃8230;やや

Question

それぞれが 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 は最小値に達する安価なオプション）。

Answer 1

これはナップザックの問題です。 （つまり、この問題の決定バージョンは、ナップザック問題の決定バージョンと同じですが、ナップザック問題の最適化バージョンは、通常とは異なります。）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 []の配列を調べてそこから推測することができます。

Answer 2

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

NPハードは不可能または高価なことを意味するものではありません。大規模な問題では、問題の解決が急速に遅くなることを意味します。アイテムが3つしかない場合、これをほんの数秒で解決できます。

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

Answer 3

編集この回答は、事実に誤りがあるため編集されます。このアドバイスに従うことは、あなたに害を及ぼすだけです。

これは実際にはナップザックの問題ではありません。これは、コンテナ内のスペースよりも多くのアイテムをパックできないことを前提としているためです。あなたの場合は、スペースがいっぱいになる最も安い組み合わせを見つけて、オーバーフローが発生する可能性を考慮したいです。

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

Amenddum これは実際にはNP完全な場合もありますが、まだわかりません。とにかく、すべての実用的な目的のために、このバリエーションは単純なソリューションよりもはるかに速いはずです。