貪欲法

Question

私はアルゴリズムに新しいですし、現在あなた管ビデオチュートリアル/講義や本を使って勉強しています、私は最初にビデオを見た後、本を読んで、最終的に確認してください、私が学んだことにするために本から質問をしてみてくださいトピックを正しく。私は現在、貪欲なアルゴリズムに悩まされており、非常に混乱しています。

は、本の中身を様々な問題がありますが、私はトラブル特定の1つを理解し、答えを持っています。

まずそれは（私は、テキストをコピーした）である問題を提供します。

サイズが{x1; x2; ..... xn}と、 容量Bのビンを含む。これらは全て正の整数である。これらのオブジェクトのサブセット を見つけて、それらの合計サイズがB以下で、できるだけBに近いサイズになるようにしてください。

すべてのオブジェクトは1次元です。たとえば、オブジェクトのサイズが4,7,10,12,15,B = 20のオブジェクトの場合は、合計サイズ19（またはそれに相当する7と12）の4と15を選択する必要があります。 次の欲張りアルゴリズムのそれぞれについて、 の反例を作成して最適でないことを示します。できるだけあなたの例を悪くしてみてください。ここで、「悪さ」 は、最適解と貪欲解の比率で測定されます。したがって、最良の ソリューションの値が10で、グリーディーソリューションの値が5の場合、比率は2です。

これはどのようにして以下のようになりますか？

1）このサイズと他のすべてのオブジェクトの合計サイズがBを超えないように、常に最大サイズのオブジェクトを選択します。残りのオブジェクトに対してこれを繰り返します。

Answer 1

が問題の次のインスタンスを想定します

あなたはサイズ2nの箱を持って、サイズn+1、残りの一つの要素は、サイズnです。

最適なのは、nの2つの要素ですが、欲張りは、n+1の要素の1つとなります。

それぞれnに該当するので、実際には少なくともこの欲張りのアプローチ2を使用して、望ましい比率を与えます。

Answer 2

これは、各項目が異なるサイズが、そのサイズ以外のビンに配置されることに任意の優先順位を持っていないいずれかの項目を意味し、同じ値を有する0-1ナップザック問題に似て聞こえます。あなたのコードでは、各アイテムを調べて、ビンの容量を超えずにビンに入れるかどうかにかかわらず最大の合計サイズを計算する必要があります。