DAA - Fractional Knapsack

Der Greedy-Algorithmus könnte mit einem bekannten Problem, das als Knapsack-Problem bezeichnet wird, sehr gut verstanden werden. Obwohl das gleiche Problem durch die Verwendung anderer algorithmischer Ansätze gelöst werden könnte, löst der Greedy-Ansatz das Fractional Knapsack-Problem in angemessener Zeit angemessen. Lassen Sie uns das Rucksackproblem im Detail diskutieren.

Rucksackproblem

Bestimmen Sie anhand einer Reihe von Elementen mit jeweils einem Gewicht und einem Wert eine Teilmenge von Elementen, die in eine Sammlung aufgenommen werden sollen, damit das Gesamtgewicht kleiner oder gleich einem bestimmten Grenzwert ist und der Gesamtwert so groß wie möglich ist.

Das Rucksackproblem liegt im kombinatorischen Optimierungsproblem. Es erscheint als Teilproblem in vielen, komplexeren mathematischen Modellen realer Probleme. Ein allgemeiner Ansatz für schwierige Probleme besteht darin, die restriktivste Einschränkung zu identifizieren, die anderen zu ignorieren, ein Rucksackproblem zu lösen und die Lösung irgendwie anzupassen, um die ignorierten Einschränkungen zu erfüllen.

Anwendungen

In vielen Fällen der Ressourcenzuweisung kann das Problem zusammen mit einigen Einschränkungen auf ähnliche Weise wie das Knapsack-Problem abgeleitet werden. Es folgt ein Beispiel.

Den am wenigsten verschwenderischen Weg finden, um Rohstoffe zu schneiden
Portfoliooptimierung
Lagerprobleme schneiden

Problemszenario

Ein Dieb raubt ein Geschäft aus und kann ein maximales Gewicht von tragen Win seinen Rucksack. Es sind n Artikel im Geschäft verfügbar und das Gewicht voni^th Artikel ist w_i und sein Gewinn ist p_i. Welche Gegenstände sollte der Dieb mitnehmen?

In diesem Zusammenhang sollten die Gegenstände so ausgewählt werden, dass der Dieb die Gegenstände trägt, für die er maximalen Gewinn erzielt. Daher ist das Ziel des Diebes, den Gewinn zu maximieren.

Aufgrund der Art der Artikel werden Rucksackprobleme als kategorisiert

Fractional Knapsack
Knapsack

Fractional Knapsack

In diesem Fall können Gegenstände in kleinere Teile zerlegt werden, daher kann der Dieb Bruchteile von Gegenständen auswählen.

Nach der Problemstellung,

Es gibt n Artikel im Laden
Gewicht von i^th item $ w_ {i}> 0 $
Gewinn für i^th item $ p_ {i}> 0 $ und
Kapazität des Rucksacks ist W

In dieser Version des Rucksackproblems können Gegenstände in kleinere Teile zerlegt werden. Der Dieb kann also nur einen Bruchteil nehmenx_i von i^th Artikel.

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

Das i^th Artikel trägt das Gewicht $ x_ {i} .w_ {i} $ zum Gesamtgewicht im Rucksack und Gewinn $ x_ {i} .p_ {i} $ zum Gesamtgewinn bei.

Daher ist das Ziel dieses Algorithmus zu

$$ maximiere \: \ displaystyle \ sum \ limit_ {n = 1} ^ n (x_ {i} .p _ {} i) $$

vorbehaltlich Einschränkungen,

$$ \ displaystyle \ sum \ limit_ {n = 1} ^ n (x_ {i} .w _ {} i) \ leqslant W $$

Es ist klar, dass eine optimale Lösung den Rucksack genau füllen muss, sonst könnten wir einen Bruchteil eines der verbleibenden Gegenstände hinzufügen und den Gesamtgewinn steigern.

Somit kann eine optimale Lösung erhalten werden durch

$$ \ displaystyle \ sum \ limit_ {n = 1} ^ n (x_ {i} .w _ {} i) = W $$

In diesem Zusammenhang müssen wir zuerst diese Elemente nach dem Wert von $ \ frac {p_ {i}} {w_ {i}} $ sortieren, so dass $ \ frac {p_ {i} +1} {w_ {i } +1} $ ≤ $ \ frac {p_ {i}} {w_ {i}} $. Hier,x ist ein Array zum Speichern des Bruchteils von Elementen.

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

Analyse

Wenn die bereitgestellten Elemente bereits in absteigender Reihenfolge von $ \ mathbf {\ frac {p_ {i}} {w_ {i}}} $ sortiert sind, benötigt der Whileloop eine Weile O(n);; Daher ist die Gesamtzeit einschließlich der Sortierung inO(n logn).

Beispiel

Betrachten wir die Kapazität des Rucksacks W = 60 und die Liste der bereitgestellten Elemente werden in der folgenden Tabelle angezeigt -

Artikel	EIN	B.	C.	D.
Profitieren	280	100	120	120
Gewicht	40	10	20	24
Verhältnis $ (\ frac {p_ {i}} {w_ {i}}) $	7	10	6	5

Da die bereitgestellten Elemente nicht nach $ \ mathbf {\ frac {p_ {i}} {w_ {i}}} $ sortiert sind. Nach dem Sortieren sind die Elemente wie in der folgenden Tabelle gezeigt.

Artikel	B.	EIN	C.	D.
Profitieren	100	280	120	120
Gewicht	10	40	20	24
Verhältnis $ (\ frac {p_ {i}} {w_ {i}}) $	10	7	6	5

Lösung

Nach dem Sortieren aller Elemente nach $ \ frac {p_ {i}} {w_ {i}} $. Zuerst alles vonB wird als Gewicht von gewählt Bist geringer als die Kapazität des Rucksacks. Nächstes ObjektA wird gewählt, da die verfügbare Kapazität des Rucksacks größer ist als das Gewicht von A. Jetzt,Cwird als nächster Punkt ausgewählt. Der gesamte Artikel kann jedoch nicht ausgewählt werden, da die verbleibende Kapazität des Rucksacks geringer ist als das Gewicht vonC.

Daher Bruchteil von C (dh (60 - 50) / 20) wird gewählt.

Jetzt entspricht die Kapazität des Rucksacks den ausgewählten Gegenständen. Daher kann kein Element mehr ausgewählt werden.

Das Gesamtgewicht der ausgewählten Artikel beträgt 10 + 40 + 20 * (10/20) = 60

Und der Gesamtgewinn ist 100 + 280 + 120 * (10/20) = 380 + 60 = 440

Dies ist die optimale Lösung. Wir können nicht mehr Gewinn erzielen, wenn wir eine andere Kombination von Gegenständen auswählen.