なぜ0/1ナップザックのためのダイナミックプログラミング？

Question

私は多くのリソースとまたthis質問を見ようとしましたが、なぜ0/1のナップザックを解決するためにダイナミックプログラミングが必要なのか混乱していますか？

質問は：私はN個のアイテムがあり、各アイテムはバリューViを持ち、各アイテムは重量Wiを持っています。私たちはWの袋を持っています。重量の限界を超えて最高の価値を得るためにアイテムを選択する方法

ダイナミックプログラミングよりもこのアプローチと混同されます：各アイテムの（値/重量）袋に残っている重量よりも重量の少ない最高の割合の商品。

Answer 1

フラクションベースのアプローチでは、反例を簡単に見つけることができます。

は

W=[3, 3, 5] 
V=[4, 4, 7] 
Wmax=6 

あなたのアプローチが最適値Vopt=7を（我々は7/5 > 4/3ので、最後の項目を取っている）を与える考えてみたが、最初の2つの項目を取ることは私たちにVopt=8を与えます。

Answer 2

ちょうどこの反例を見て：他の回答が指摘したように

Weight 7, W/V pairs (3/10),(4/12),(5/21) 

Answer 3

、あなたのアプローチとエッジケースがあります。

私はあなたがこの推論でそれに近づく示唆少し良く再帰的な解決策を説明するために、そしておそらくそれをよりよく理解するために：

それぞれ「subsack」

1. のために、我々はそこにはフィッティングの要素を持っていない場合
2. フィッティング要素が1つのみの場合、要素は
3. です。複数のフィッティング要素がある場合は、各要素を取り、その「サブスタック」に最適なフィッティングを計算します。最良の選択肢は、最も価値の高い要素/サブパッケージの組み合わせです。

このアルゴリズムは、フィッティング要素のすべての可能な組み合わせにまたがり、最も高い値を持つものを見つけるために機能します。

代わりに、直接解決策はthe problem is NP-hardとして使用できません。

Answer 4

ユニットレシオの場合、欲張りアルゴリズムが失敗します。それは貪欲アルゴリズムによれば

N = 1 2、P = 4〜18、W = 2 18、P/W = 2 1

ナップザック容量= 18

ます。例えば、次の例を考えます最初の項目はP/W比が大きいので考慮してください。したがって、総利益は4です（最初の項目を挿入した後に容量が16に減少するため、最初に2番目の項目を挿入できないため）。我々は0/1ナップザック問題で動的なプログラミングを使用する理由

しかし、実際の答えは18

したがって貪欲に最適なソリューションを提供するために失敗した複数のコーナーケースがあるが、それはです。