0-1ナップザックの該当するミートンアルゴリズムを実現する方法

Question

私は今KnapSackの問題（kp）を研究していて、 Wikipedia $ o ^ *の理論的な時間の複雑さでそれを実現する方法、それを実現する方法はほとんど不明瞭です。 2）$ ？私は0-1 kpの特定のインスタンスであるサブセット合計問題（SSP）のアルゴリズムを理解することができますが、一般化された問題のためにステップ：

  for each subset of A do
      find the subset of B of greatest value such that the combined weight is less than W

.

理解しているように、これは（例えば、バイナリ検索）を検索することです.Bのすべてのサブセットの合計重みに、検索ごとに対数時間がかかります。しかし、どのサブセットがWよりも小さい重みがあるかを知った後、最大の値の1つを見つける方法は？重み $ o ^ *（2 ^ {n / 2}）$ ですが、 $ O ^ *（2 ^ n）$ 。

それが結合重みを狭くしないと、まず狭い値のサブセットを見つけたとしても、重みの検証はおそらく誤って誤りを変えるでしょう、したがって他のサブセットにもっと多くのテストが必要であり、数字のサイズに再び直線的に関連付けられているようです。

今すぐ私は合計値と組み合わされた重みが強く正の相関していると仮定することができるので、最大許容重量でサブセットを見つけた後、最大値の1つの間でこのサブセットを検索するのに一定の時間のみが必要です。しかし、私はこの説明に満足していません。だから誰でもこの問題についての良いアイデアがありますか？

PS：ホロウィッツ、エリス、Sahni、Sartajによって元の論文を読みましたが、共通の最適化問題よりもむしろ決定的な問題があると定義された問題が見つかりました。多分誰かがこの方向にアイデアを提供することができます。

Answer 1

最初に、 $ b $ のすべてのサブセットの重みを事前に事前に予めます。

重量でソートし、 $ w [i]=重み$ と $ s [i]=サブセット$ 。

$ Best [i] $ がindex $ j $ です。 $ j <= i $ に設定されている最大値のセット。 $ i= 0 $ からの単一のスキャンでこれを行うことができます。これまでのところ、すべてのステップでこれまでに見られた最大値を記憶します。

今、 $ b $ を検索するには、 $ w $ でバイナリ検索を行います。最大許容重み、および $ best $

の同じインデックスから最適なセットを取得します。