線形時間の分数ナップザックを解く方法は？これは Google で見つけましたが、よくわかりません。

  1. $ R $からランダムに要素$ r $を選択してください。 （利益/重量比のセット）
  2. 決定
    • $ R_1 = \ {p_i / w_i | p_i / w_i > r、1 \ leq i \ leq n \}、W_1 = \ sum_ {i \ in R_1} w_i $
    • $ R_2 = \ {p_i / w_i | p_i / w_i = r、for 1 \ leq i \ leq n \}、W_2 = \ sum_ {i \ in R_3} w_i $
    • $ R_3 = \ {p_i / w_i | p_i / w_i < r、for 1 \ leq i \ leq n \}、W_3 = \ sum_ {i \ in R_3} w_i $
  3. if $ W_1 > W $
    • $ R_1 $を繰り返し、計算された解を返します
  4. else
    • while（ナップザックと$にスペースがありますR_2 $は空ではありません）
      • $ R_2 $からアイテムを追加します
    • if（ナップサックがいっぱいになります）
      • $ R_1にアイテムを返します$と$ R_2 $から追加されたばかりのアイテム
    • else
      • ナップザックの容量を$ W_1 + W_2 $削減します
      • $で繰り返しますR_3 $および$ R_1 \ cuの返品アイテムp R_2 $
      • 再帰呼び出しから返されたアイテムを追加する

方法がわかりません動作します、$ R $と$ W $は何を表すことになっています…誰かが説明できますか？または、提案する別のアルゴリズムがある場合はどうでしょうか。

回答

問題を述べていただければ幸いです。 $ n $ のアイテム $ x_i $ があり、それぞれに利益があると仮定します $ p_i $ と重み $ w_i $ 。総重量が最大で $ W $ であるという制約の下で、利益を最大化する必要があります。各アイテム $ x_i $ について、任意の分数 $ \ theta \ in [0,1] $ <を入れることができます。 / span>は、利益 $ \ theta p_i $ と重み $ \ theta w_i $ 。

これが例です。生の金があり、利益は $ 1000 $ 、重量は $ 1 $ です。バナナもあり、利益は $ 1 $ 、重量は $ 10 $ です。 $ 2 $ の重さを運ぶことができると仮定します。あなたならどうしますか？当然のことながら、最初にできるだけ多くの金、つまりすべてを入れ、次にできるだけ多くのバナナ、つまり10分の1を入れて、合計利益を $ 1000.1 $ 。

一般的なアルゴリズムも同様です。 $ W $ を $ 1000 $ の「スロット」に分割するとします。収益性の高いアイテム-重量の一部 $ W / 1000 $ 。 $ w_i $ の重さのアイテムの場合、 $ w_i /（W / 1000）$ 個があります（今のところ、これは整数です）、それぞれが $ p_i /（w_i /（W / 1000））$ の価値があります。スロットに何を入れるかを選ぶときは、利益を最大にしたいので、 $ p_i / w_i $ が最大のアイテムを選び、できるだけ多く入れます。可能な限りピース。不足した場合は、次に大きい $ p_i / w_i $ のアイテムを選択します。

これは分割せずに実装できます。 $ W $ を $ 1000 $ 個に分割：最大の $ p_i / w_i $ 、そしてできるだけ多く入れてください。足りなくなったら、次のものを選んで、できるだけたくさん入れてください。等々。このアルゴリズムを実装するには、リスト $ p_i / w_i $ を並べ替える必要があり、これには時間がかかります $ O（n \ log n）$ 。説明するアルゴリズムは、クイックセレクトで使用するのと同じトリックを使用して、アルゴリズムをランダム化する代わりに、実行時間を $ O（n）$ に短縮します。

アルゴリズムを理解するには、次のルートをお勧めします。

  1. フラクショナルナップザックの古典的な欲張りアルゴリズムを理解します。
  2. クイックセレクトを理解します。
  3. 引用するアルゴリズムが、クイックセレクトの手法と欲張りアプローチをどのように組み合わせているかをご覧ください。

回答

R は、すべてのオブジェクトの利益/重量の比率のセットであり、オブジェクトの利益と重量が示されます。そして、 W はナップザックの容量です。
これで、1ステップでランダムな要素を選択する代わりに、中央値検出アルゴリズムをに適用できます。 O（n）回の中央値を見つけます。
これで、残りのすべての手順を実行できます。したがって、時間計算量の分析は次のようになります-
        T（n）= T（n / 2）+ O（n）。
そして、解決策として O（n）を取得します。何かが適切に説明されておらず、もっと知りたい場合は教えてください。

回答

線形時間で、単位重量あたりの値に関する中央値の項目。次に、線形時間でも、少なくともその価値のあるすべてのアイテムをナップザックに収めることができるかどうかを判断できます。可能であれば、そうして、 n / 2 の値の低いアイテムについてこの問題を再帰的に解決してください。」すでにナップザックを埋めています。できない場合は、値の低い n / 2 アイテムを捨てることができます。次に、最も価値の高い n / 2 アイテムのみを使用して問題の解決を再試行します。

ここでの再帰は T（n）= T（n / 2）+ O（n）であり、 T（n）= O（n）、必要に応じて。

貼り付けたソリューション： R は比率のセットであり、利益/重み W はこのセットの全体の重みの合計です、ナップザックの容量と比較するために使用されます。同様に、{pi / wi | pi / wi}は、利益がi番目の重み値に対するi番目の要素を表します。この値をランダムに選択された r 値と比較し、比率の比較に基づいて分離しています。 R1、R2、R3 は、比率が以下、等しい、または大きい場合に応じて、比率セットのサブセットになります。中央値要素。

同様に、 W1、W2、W3 は、これらのセットの重みの合計です。

ここで、最初に説明したように、比率の値に応じて適切なソリューションセットを選択します。

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です