DAA-フラクショナルナップザック

欲張りアルゴリズムは、ナップサック問題と呼ばれるよく知られた問題で非常によく理解できます。同じ問題は他のアルゴリズムアプローチを採用することで解決できますが、欲張りアプローチはフラクショナルナップサック問題を適度に解決します。ナップサック問題について詳しく説明しましょう。

ナップサック問題

それぞれに重みと値を持つアイテムのセットが与えられた場合、コレクションに含めるアイテムのサブセットを決定して、合計の重みが指定された制限以下になり、合計値が可能な限り大きくなるようにします。

ナップサック問題は、組み合わせ最適化問題にあります。これは、実世界の問題の多くのより複雑な数学的モデルのサブ問題として表示されます。難しい問題に対する一般的なアプローチの1つは、最も制限の厳しい制約を特定し、他の制約を無視し、ナップサック問題を解決し、無視された制約を満たすようにソリューションを調整することです。

アプリケーション

いくつかの制約を伴うリソース割り当ての多くの場合、問題はナップサック問題と同様の方法で導き出すことができます。以下は一組の例です。

原材料をカットするための最も無駄の少ない方法を見つける
ポートフォリオの最適化
板取り問題

問題シナリオ

泥棒が店を奪っていて、最大重量を運ぶことができます W彼のナップザックに。店内にはn個の商品があり、i^th アイテムは w_i そしてその利益は p_i。泥棒はどのようなアイテムを取るべきですか？

この文脈では、アイテムは、泥棒が最大の利益を得るアイテムを運ぶように選択する必要があります。したがって、泥棒の目的は利益を最大化することです。

アイテムの性質に基づいて、ナップサック問題は次のように分類されます。

フラクショナルナップザック
Knapsack

フラクショナルナップザック

この場合、アイテムを細かく分割できるため、泥棒はアイテムの一部を選択できます。

問題の説明によると、

がある n ストア内のアイテム
の重量 i^th アイテム$ w_ {i}> 0 $
の利益 i^th アイテム$ p_ {i}> 0 $および
ナップザックの容量は W

このバージョンのナップサック問題では、アイテムを細かく分割できます。だから、泥棒はほんの一部しか取ることができませんx_i の i^th 項目。

$$ 0 \ leqslant x_ {i} \ leqslant 1 $$

ザ・ i^th アイテムは、重量$ x_ {i} .w_ {i} $をナップザックの総重量に、利益$ x_ {i} .p_ {i} $を総利益に貢献します。

したがって、このアルゴリズムの目的は

$$ maximum \：\ displaystyle \ sum \ limits_ {n = 1} ^ n（x_ {i} .p _ {} i）$$

制約の対象、

$$ \ displaystyle \ sum \ Limits_ {n = 1} ^ n（x_ {i} .w _ {} i）\ leqslant W $$

最適なソリューションがナップザックを正確に満たす必要があることは明らかです。そうしないと、残りのアイテムの1つの一部を追加して、全体的な利益を増やすことができます。

したがって、最適解は次の方法で取得できます。

$$ \ displaystyle \ sum \ Limits_ {n = 1} ^ n（x_ {i} .w _ {} i）= W $$

このコンテキストでは、最初に$ \ frac {p_ {i}} {w_ {i}} $の値に従ってこれらのアイテムを並べ替えて、$ \ frac {p_ {i} + 1} {w_ {i } + 1} $≤$ \ frac {p_ {i}} {w_ {i}} $。ここに、x アイテムの端数を格納する配列です。

Algorithm: Greedy-Fractional-Knapsack (w[1..n], p[1..n], W) 
for i = 1 to n 
   do x[i] = 0 
weight = 0 
for i = 1 to n 
   if weight + w[i] ≤ W then  
      x[i] = 1 
      weight = weight + w[i] 
   else 
      x[i] = (W - weight) / w[i] 
      weight = W 
      break 
return x

分析

提供されたアイテムがすでに$ \ mathbf {\ frac {p_ {i}} {w_ {i}}} $の降順で並べ替えられている場合、whileループには時間がかかります。 O(n); したがって、並べ替えを含む合計時間はO(n logn)。

例

ナップザックの容量を考えてみましょう W = 60 提供されたアイテムのリストを次の表に示します-

項目	A	B	C	D
利益	280	100	120	120
重量	40	10	20	24
比率$（\ frac {p_ {i}} {w_ {i}}）$	7	10	6	5

提供されたアイテムは$ \ mathbf {\ frac {p_ {i}} {w_ {i}}} $に基づいてソートされていないため。並べ替え後の項目は次の表のようになります。

項目	B	A	C	D
利益	100	280	120	120
重量	10	40	20	24
比率$（\ frac {p_ {i}} {w_ {i}}）$	10	7	6	5

解決

$ \ frac {p_ {i}} {w_ {i}} $に従ってすべてのアイテムを並べ替えた後。まず最初にB の重量として選択されます Bナップザックの容量よりも少ないです。次に、アイテムA ナップザックの利用可能な容量がの重量よりも大きいため、が選択されます A。さて、C次の項目として選択されます。ただし、ナップザックの残り容量が重量より少ないため、アイテム全体を選択することはできません。C。

したがって、 C （つまり、（60 − 50）/ 20）が選択されます。

これで、ナップザックの容量は選択したアイテムと同じになります。したがって、これ以上アイテムを選択することはできません。

選択したアイテムの総重量は 10 + 40 + 20 * (10/20) = 60

そして総利益は 100 + 280 + 120 * (10/20) = 380 + 60 = 440

これが最適なソリューションです。アイテムの異なる組み合わせを選択しても、これ以上の利益を得ることができません。