私は次のテストのレビューを検討していて、誰かが質問のパートbを言い直すことができるかどうか疑問に思っていました。これは渡されたレビューシートのテキストですが、パートbが正確に何を求めているのかわかりません。「0/1ナップサック問題に最適な解が1％未満になる」とは、もっと厳密に言うとどういう意味かと思います。
a）ナップサック問題の次の例を解きます。つまり、選択した各オブジェクトの割合と最適なナップサックの値を与えます。手順を表示する：
ナップザックの容量はC=100です
**ここで、彼はオブジェクト、それらの値、および重みをリストします。テーブルで**
b）[10pts]フラクショナルナップサック問題に使用された同じ欲張り法（欲張り法によって選択された最後のオブジェクトが適合しない場合は除外するようにわずかに変更）が次のような解をもたらすことを示す2つのオブジェクトの例を示します。 0/1ナップサック問題の最適値の1％未満。
通常、貪欲なヒューリスティックは、ナップザックの問題に対して非常にうまく機能します。小さな問題インスタンスを無作為に思いついただけの場合、貪欲なヒューリスティックを適用すると、適切な、または場合によっては最適なソリューションが生成される可能性があります。(ソリューションの品質は、含まれるオブジェクトの合計値を取得し、最適なソリューションに含まれるオブジェクトの合計値に対する比率を計算することによって測定されます。)
この質問は、貪欲なヒューリスティックを非常に混乱させ、それを適用すると、最適解に含まれる値の 1% しか含まれていないナップサックが生成される厄介な問題インスタンス (つまり、値と重みを持つオブジェクトのリスト) を考え出すことを求めています。 .
私は、欲張りアルゴリズムが最適ではなく、さらに最適値の1％未満しか得られないことを示すことを要求するパートb）を理解しています。これはすでに小さなインスタンスの場合です。次の例を考えてみましょう。
Item 1: profit 2, weight 1 (efficiency is 2/1 = 200/100 = 2)
Item 2: profit 400, weight 400 (efficiency is 400/400 = 1)
Knapsack capacity: 400
アイテムは、欲張りアルゴリズムがそれらを処理する順序である効率の増加しない順序で与えられることに注意してください。これで、欲張りアルゴリズムはアイテム1を選択しますが、アイテム2は選択できません。これにより、2の利益が得られます。ただし、項目2を選択すると400の利益が得られます。合計で、欲張りアルゴリズムは2の利益をもたらし、最適値は少なくとも400であるため、欲張りアルゴリズムは1％未満の利益をもたらします。最適な利益。
ナップザック問題は NP に属します。2番目の部分では、最適解とわずか1％異なる解を与える貪欲な戦略（最適解は指数時間の複雑さである）に基づく多項式時間近似アルゴリズムを求めていると思います。
たとえば、最適な答えが 100 の場合、近似アルゴリズムは 99 または 101 の結果を与える必要があります。