Fractionele knapzak Probleem: hebzuchtig algoritme met voorbeeld
Sara Chen
Wat is hebzuchtige strategie?
Hebzuchtige algoritmen zijn vergelijkbaar met dynamische programmeeralgoritmen die vaak worden gebruikt om optimale problemen op te lossen (de beste oplossingen voor een probleem vinden op basis van een bepaald criterium).
Greedy-algoritmen implementeren optimale lokale selecties in de hoop dat die selecties zullen leiden tot een optimale globale oplossing voor het op te lossen probleem. Greedy-algoritmen zijn vaak niet al te moeilijk om op te zetten, snel (tijdscomplexiteit is vaak een lineaire functie of een tweede-orde functie). Bovendien zijn deze programma's niet moeilijk te debuggen en gebruiken ze minder geheugen. Maar de resultaten zijn niet altijd een optimale oplossing.
Hebzuchtige strategieën worden vaak gebruikt om het combinatorische optimalisatieprobleem op te lossen door een optie A te bouwen. Optie A wordt geconstrueerd door elke component Ai van A te selecteren totdat deze voltooid is (genoeg n componenten). Voor elke Ai kies je optimaal Ai. Op deze manier is het mogelijk dat u bij de laatste stap niets anders hoeft te selecteren dan de laatst overgebleven waarde te accepteren.
Er zijn twee cruciale componenten van hebzuchtige beslissingen:
- Manier van hebzuchtige selectie. U kunt selecteren welke oplossing op dit moment het beste is en vervolgens het subprobleem oplossen dat voortvloeit uit het maken van de laatste selectie. De selectie van hebzuchtige algoritmen kan afhankelijk zijn van eerdere selecties. Maar het kan niet afhankelijk zijn van toekomstige selecties of van de oplossingen van subproblemen. Het algoritme evolueert op een manier die selecties in een lus maakt, terwijl het gegeven probleem tegelijkertijd wordt verkleind tot kleinere subproblemen.
- Optimale onderbouw. Je voert de optimale onderbouw voor een probleem uit als de optimale oplossing van dit probleem optimale oplossingen voor de deelproblemen bevat.
Een hebzuchtig algoritme bestaat uit vijf componenten:
- Een reeks kandidaten waaruit oplossingen kunnen worden gecreëerd.
- Een selectiefunctie, om de beste kandidaat te selecteren om aan de oplossing toe te voegen.
- Er wordt gebruik gemaakt van een haalbare functie om te beslissen of een kandidaat kan worden gebruikt om een oplossing te bouwen.
- Een objectieve functie, die de waarde van een oplossing of een onvolledige oplossing vaststelt.
- Een evaluatiefunctie, die aangeeft wanneer u een complete oplossing vindt.
Het idee van hebzuchtige
Met het eerste idee heb je de volgende stappen van Greedy One:
- Sorteer in niet-oplopende volgorde van waarden.
- Beschouw op zijn beurt de bestelde pakketten, stop het betreffende pakket in de knapzak als de resterende capaciteit van de knapzak voldoende is om het te bevatten (wat betekent dat het totale gewicht van de pakketten die in de knapzak zijn gestopt en het gewicht van de te overwegen pakketten niet groter zijn dan de capaciteit van de knapzak).
Dit hebzuchtige algoritme geeft echter niet altijd de optimale oplossing. Hier heb je een tegenvoorbeeld:
- De parameters van het probleem zijn: n = 3; M = 19.
- De pakketten: {i = 1; W[ik] = 14; V[i] = 20}; {ik = 2; W[ik] = 6; V[i] = 16}; {ik = 3; W[ik] = 10; V[ik] = 8} -> Grote waarde, maar ook een groot gewicht.
- Het algoritme selecteert pakket 1 met een totale waarde van 20, terwijl de optimale oplossing van het probleem wordt geselecteerd (pakket 2, pakket 3) met een totale waarde van 24.
Het idee van Greedy Two
Met het tweede idee heb je de volgende stappen van Greedy Two:
- Sorteer in niet-aflopende volgorde van gewichten.
- Beschouw op zijn beurt de bestelde pakketten, stop het betreffende pakket in de knapzak als de resterende capaciteit van de knapzak voldoende is om het te bevatten (wat betekent dat het totale gewicht van de pakketten die in de knapzak zijn gestopt en het gewicht van de te overwegen pakketten niet groter zijn dan de capaciteit van de knapzak).
Dit hebzuchtige algoritme geeft echter niet altijd de optimale oplossing. Hier heb je een tegenvoorbeeld:
- De parameters van het probleem zijn: n = 3; M = 11.
- De pakketten: {i = 1; W[ik] = 5; V[i] = 10}; {ik = 2; W[ik] = 6; V[i] = 16}; {ik = 3; W[ik] = 10; V[ik] = 28} -> Licht van gewicht, maar de waarde is ook erg licht.
- Het algoritme selecteert (pakket 1, pakket 2) met een totale waarde van 26, terwijl de optimale oplossing van het probleem (pakket 3) is met een totale waarde van 28.
Het idee van hebzuchtige drie
Met het derde idee heb je de volgende stappen van Greedy Three. Dit is in feite het meest gebruikte algoritme.
- Sorteer pakketten in de volgorde waarin de waarde van de eenheidskosten niet stijgt
. Je hebt:
- Beschouw op zijn beurt de bestelde pakketten, stop het betreffende pakket in de knapzak als de resterende capaciteit van de knapzak voldoende is om het te bevatten (wat betekent dat het totale gewicht van de pakketten die in de knapzak zijn gestopt en het gewicht van de te overwegen pakketten niet groter zijn dan de capaciteit van de knapzak).
Het idee: Het hebzuchtige idee van dat probleem is het berekenen van de 
verhouding van elk 
. Sorteer deze verhoudingen vervolgens in aflopende volgorde. Je kiest het hoogste pakket en de capaciteit van de knapzak kan dat pakket bevatten (blijft > wi). Elke keer dat er een pakketje in de knapzak wordt gedaan, vermindert ook de capaciteit van de knapzak.
Manier om de pakketten te selecteren:
- Denk aan de reeks eenheidskosten. Je selecteert pakketten op basis van afnemende eenheidskosten.
- Stel dat je een deeloplossing hebt gevonden: (x1, ..., Xi).
- De waarde van de knapzak wordt verkregen:
- Komt overeen met het gewicht van de pakketten die in de knapzak zijn gestopt:
- Daarom is de resterende gewichtslimiet van de knapzak:
Stappen van algoritme
Je ziet dat dit een probleem is bij het vinden van max. De lijst met pakketten is gesorteerd in aflopende volgorde van eenheidskosten om vertakkingen te kunnen overwegen.
- Stap 1: De knooppuntwortel vertegenwoordigt de beginstatus van de knapzak, waarin u geen enkel pakket hebt geselecteerd.
- Totale waarde = 0.
- De bovengrens van het hoofdknooppunt UpperBound = M * Maximale eenheidskosten.
- Stap 2: De knooppuntroot heeft onderliggende knooppunten die overeenkomen met de mogelijkheid om het pakket met de hoogste eenheidskosten te selecteren. Voor elk knooppunt herberekent u de parameters:
- TotalValue = TotalValue (oud) + aantal geselecteerde pakketten * waarde van elk pakket.
- M = M (oud) – aantal geselecteerde pakketten * gewicht van elk pakket.
- UpperBound = TotalValue + M (nieuw) * De eenheidskosten van het pakket waarmee rekening wordt gehouden.
- Stap 3: In onderliggende knooppunten geeft u prioriteit aan vertakkingen voor het knooppunt met de grootste bovengrens. De kinderen van dit knooppunt komen overeen met het vermogen om het volgende pakket met hoge eenheidskosten te selecteren. Voor elk knooppunt moet u de parameters TotalValue, M, UpperBound opnieuw berekenen volgens de formule uit stap 2.
- Stap 4: Herhaal stap 3 met de opmerking: voor knooppunten met een bovengrens die lager is of gelijk is aan de tijdelijke maximale kosten van een gevonden optie, hoeft u voor dat knooppunt niet meer te vertakken.
- Stap 5: Als alle knooppunten vertakt of afgesneden zijn, is de duurste optie degene om naar te zoeken.
Pseudocode voor het algoritme:
Fractional Knapsack (Array W, Array V, int M) 1. for i <- 1 to size (V) 2. calculate cost[i] <- V[i] / W[i] 3. Sort-Descending (cost) 4. i ← 1 5. while (i <= size(V)) 6. if W[i] <= M 7. M ← M – W[i] 8. total ← total + V[i]; 9. if W[i] > M 10. i ← i+1
De complexiteit van het algoritme:
- Als je een eenvoudig sorteeralgoritme gebruikt (selectie, bubbel…), dan is de complexiteit van het hele probleem O(n2).
- Als u snel sorteren of samenvoegen gebruikt, is de complexiteit van het hele probleem O(nlogn).
Java code voor Greedy Three
- Eerst definieer je klasse KnapsackPackage. Deze klasse heeft eigenschappen als: gewicht, waarde en bijbehorende kosten van elk pakket. De vastgoedkosten van deze klasse worden gebruikt voor sorteertaken in het hoofdalgoritme. De waarde van elke kost is de
verhouding van elk pakket.
public class KnapsackPackage {
private double weight;
private double value;
private Double cost;
public KnapsackPackage(double weight, double value) {
super();
this.weight = weight;
this.value = value;
this.cost = new Double(value / weight);
}
public double getWeight() {
return weight;
}
public double getValue() {
return value;
}
public Double getCost() {
return cost;
}
}
- Vervolgens maakt u een functie om het algoritme Greedy Three uit te voeren.
public void knapsackGreProc(int W[], int V[], int M, int n) {
KnapsackPackage[] packs = new KnapsackPackage[n];
for (int i = 0; i < n; i ++) {
packs[i] = new KnapsackPackage(W[i], V[i]);
}
Arrays.sort(packs, new Comparator<KnapsackPackage>() {
@Override
public int compare(KnapsackPackage kPackA, KnapsackPackage kPackB) {
return kPackB.getCost().compareTo(kPackA.getCost());
}
});
int remain = M;
double result = 0d;
int i = 0;
boolean stopProc = false;
while (!stopProc) {
if (packs[i].getWeight() <= remain) {
remain -= packs[i].getWeight();
result += packs[i].getValue();
System.out.println("Pack " + i + " - Weight " + packs[i].getWeight() + " - Value " + packs[i].getValue());
}
if (packs[i].getWeight() > remain) {
i ++;
}
if (i == n) {
stopProc = true;
}
}
System.out.println("Max Value:\t" + result);
}
Toelichting code:
- Initialiseer het gewicht en de waarde voor elk knapzakpakket.
- Sorteer knapzakpakketten op prijs in aflopende volgorde.
- Als u pakket i.
- Als u het aantal pakketten selecteert, is i voldoende.
- Stop met het bladeren door alle pakketten.
In deze zelfstudie vindt u twee voorbeelden. Hier is Java-code om het bovenstaande programma uit te voeren met twee voorbeelden:
public void run() {
/*
* Pack and Weight - Value
*/
//int W[] = new int[]{15, 10, 2, 4};
int W[] = new int[]{12, 2, 1, 1, 4};
//int V[] = new int[]{30, 25, 2, 6};
int V[] = new int[]{4, 2, 1, 2, 10};
/*
* Max Weight
*/
//int M = 37;
int M = 15;
int n = V.length;
/*
* Run the algorithm
*/
knapsackGreProc(W, V, M, n);
}
Je hebt de uitvoer:
- Eerste voorbeeld:
Pack 0 - Weight 10.0 - Value 25.0 Pack 0 - Weight 10.0 - Value 25.0 Pack 0 - Weight 10.0 - Value 25.0 Pack 2 - Weight 4.0 - Value 6.0 Pack 3 - Weight 2.0 - Value 2.0 Max Value: 83.0
- Tweede voorbeeld:
Pack 0 - Weight 4.0 - Value 10.0 Pack 0 - Weight 4.0 - Value 10.0 Pack 0 - Weight 4.0 - Value 10.0 Pack 1 - Weight 1.0 - Value 2.0 Pack 1 - Weight 1.0 - Value 2.0 Pack 1 - Weight 1.0 - Value 2.0 Max Value: 36.0
Analyseer het eerste voorbeeld:
- De parameters van het probleem zijn: n = 4; M = 37.
- De pakketten: {i = 1; W[ik] = 15; V[i] = 30; Kosten = 2.0}; {ik = 2; W[ik] = 10; V[ik] = 25; Kosten = 2.5}; {ik = 3; W[ik] = 2; V[ik] = 4; Kosten = 1.0}; {ik = 4; W[ik] = 4; V[i] = 6; Kosten = 1.5}.
- Je sorteert pakketten in de volgorde waarin de waarde van de eenheidskosten niet stijgt. Je hebt: {i = 2} -> {ik = 1} -> {ik = 4} -> {ik = 3}.
Stappen voor het toepassen van het algoritme voor het eerste voorbeeld:
- Definieer x1, x2, x3, x4 als het nummer van elk geselecteerd pakket, overeenkomend met pakket {i = 2} -> {ik = 1} -> {ik = 4} -> {ik = 3}.
- Knooppunt N vertegenwoordigt de status waarin u geen pakket hebt geselecteerd. Dan:
- Totale waarde = 0.
- M = 37 (zoals voorgesteld).
- Bovengrens = 37 * 2.5 = 92.5, waarvan 37 M is en 2.5 de eenheidskosten van pakket {i = 2}.
- Met pakket {i = 2} heb je 4 mogelijkheden: selecteer 3 pakketten {i = 2} (x1 = 3); selecteer 2 pakketten {i = 2} (x1 = 2); selecteer 1 pakket {i = 2} (x1 = 1) en selecteer niet pakket {i = 2} (x1 = 0). In overeenstemming met deze 4 mogelijkheden vertak je het wortelknooppunt N naar 4 kinderen N[1], N[2], N[3] en N[4].
- Voor kindknooppunt N1 heeft u:
- TotalValue = 0 + 3 * 25 = 75, waarbij 3 het aantal geselecteerde pakketten {i = 2} is en 25 de waarde van elk pakket {i = 2}.
- M = 37 – 3 * 10 = 7, waarbij 37 de initiële hoeveelheid van de knapzak is, 3 het aantal pakketten is {i = 2}, 10 het gewicht van elk pakket is {i = 2}.
- Bovengrens = 75 + 7 * 2 = 89, waarbij 75 de Totale Waarde is, 7 het resterende gewicht van de knapzak en 2 de eenheidskosten van het pakket {i = 1}.
- Op dezelfde manier kunt u de parameters berekenen voor knooppunten N[2], N[3] en N[4], waarbij de bovengrens respectievelijk 84, 79 en 74 is.
- Van de knooppunten N[1], N[2], N[3] en N[4] heeft knooppunt N[1] de grootste bovengrens, dus je vertakt knooppunt N[1] eerst in de hoop dat er een Goed plan vanuit deze richting.
- Van knooppunt N[1] heb je slechts één onderliggend knooppunt N[1-1] dat overeenkomt met x2 = 0 (vanwege het resterende gewicht van de rugzak is 7, terwijl het gewicht van elk pakket {i = 1} 15 is) . Nadat u de parameters voor de N[1-1]-knop hebt bepaald, is de bovengrens van N[1-1] 85.5.
- Je gaat verder met het vertakken van knooppunt N[1-1]. Knooppunt N[1-1] heeft 2 kinderen N[1-1-1] en N[1-1-2] die overeenkomen met x3 = 1 en x3 = 0. Nadat u de parameters voor deze twee knooppunten hebt bepaald, ziet u dat de De bovengrens van N[1-1-1] is 84 en die van N[1-1-2] is 82, dus je gaat door met het aftakken van knooppunt N[1-1-1].
- Knooppunt N[1-1-1] heeft twee kinderen, N[1-1-1-1] en N[1-1-1-2], overeenkomend met x4 = 1 en x4 = 0. Dit zijn twee bladknooppunten (die de optie vertegenwoordigt) omdat voor elk knooppunt het aantal pakketten is geselecteerd. Waarbij knooppunt N[1-1-1-1] de optie x1 = 3, x2 = 0, x3 = 1 en x4 = 1 voor 83 vertegenwoordigt, terwijl knooppunt N[1-1-1-2] de optie x1 vertegenwoordigt = 3, x2 = 0, x3 = 1 en x4 = 01 bij 81. De tijdelijke maximale waarde hier is dus 83.
- Als je terugkeert naar knooppunt N[1-1-2], zie je dat de bovengrens van N[1-1-2] 82 < 83 is, dus trim je knooppunt N[1-1-2].
- Als u terugkeert naar knooppunt N2, ziet u dat de bovengrens van N2 84 > 83 is, dus u gaat verder met het aftakken van knooppunt N2. Het knooppunt N2 heeft twee kinderen N[2-1] en N[2-2] die overeenkomen met x2 = 1 en x2 = 0. Na het berekenen van de parameters voor N[2-1] en N[2-2] ziet u de bovengrens van N[2-1] is 83 en die van N[2-2] is 75.25. Geen van deze waarden is groter dan 83, dus beide knooppunten worden bijgesneden.
- Ten slotte worden ook de knooppunten N3 en N4 bijgesneden.
- Alle knooppunten in de boom zijn dus vertakt of bijgesneden, dus de beste tijdelijke oplossing is degene waar u naar moet zoeken. Dienovereenkomstig moet u 3 pakketten {i = 2}, 1 pakket {i = 4} en één pakket {i = 3} met een totale waarde van 83 selecteren, het totale gewicht is 36.
Met dezelfde analyse van het tweede voorbeeld heb je het resultaat: selecteer pakket 4 (3 keer) en pakket 5 (3 keer).
Python3-code voor Greedy Three
- Eerst definieer je klasse KnapsackPackage.
class KnapsackPackage(object):
""" Knapsack Package Data Class """
def __init__(self, weight, value):
self.weight = weight
self.value = value
self.cost = value / weight
def __lt__(self, other):
return self.cost < other.cost
- Vervolgens maakt u een functie om het algoritme Greedy Three uit te voeren.
class FractionalKnapsack(object):
def __init__(self):
def knapsackGreProc(self, W, V, M, n):
packs = []
for i in range(n):
packs.append(KnapsackPackage(W[i], V[i]))
packs.sort(reverse = True)
remain = M
result = 0
i = 0
stopProc = False
while (stopProc != True):
if (packs[i].weight <= remain):
remain -= packs[i].weight;
result += packs[i].value;
print("Pack ", i, " - Weight ", packs[i].weight, " - Value ", packs[i].value)
if (packs[i].weight > remain):
i += 1
if (i == n):
stopProc = True
print("Max Value:\t", result)
Toelichting code:
- Initialiseer het gewicht en de waarde voor elk knapzakpakket.
- Sorteer knapzakpakketten op prijs in aflopende volgorde.
- Als u pakket i.
- Als u het aantal pakketten selecteert, is i voldoende.
- Stop met het bladeren door alle pakketten.
Hier is Python3-code om het bovenstaande programma uit te voeren met het eerste voorbeeld:
if __name__ == "__main__":
W = [15, 10, 2, 4]
V = [30, 25, 2, 6]
M = 37
n = 4
proc = FractionalKnapsack()
proc.knapsackGreProc(W, V, M, n)
Je hebt de uitvoer:
Pack 0 - Weight 10 - Value 25 Pack 0 - Weight 10 - Value 25 Pack 0 - Weight 10 - Value 25 Pack 2 - Weight 4 - Value 6 Pack 3 - Weight 2 - Value 2 Max Value: 83
C#-code voor Greedy Three
- Eerst definieer je klasse KnapsackPackage.
using System;
namespace KnapsackProblem
{
public class KnapsackPackage
{
private double weight;
private double value;
private double cost;
public KnapsackPackage(double weight, double value)
{
this.weight = weight;
this.value = value;
this.cost = (double) value / weight;
}
public double Weight
{
get { return weight; }
}
public double Value
{
get { return value; }
}
public double Cost
{
get { return cost; }
}
}
}
- Vervolgens maakt u een functie om het algoritme Greedy Three uit te voeren.
using System;
namespace KnapsackProblem
{
public class FractionalKnapsack
{
public FractionalKnapsack()
{
}
public void KnapsackGreProc(int[] W, int[] V, int M, int n)
{
KnapsackPackage[] packs = new KnapsackPackage[n];
for (int k = 0; k < n; k++)
packs[k] = new KnapsackPackage(W[k], V[k]);
Array.Sort<KnapsackPackage>(packs, new Comparison<KnapsackPackage>(
(kPackA, kPackB) => kPackB.Cost.CompareTo(kPackA.Cost)));
double remain = M;
double result = 0d;
int i = 0;
bool stopProc = false;
while (!stopProc)
{
if (packs[i].Weight <= remain)
{
remain -= packs[i].Weight;
result += packs[i].Value;
Console.WriteLine("Pack " + i + " - Weight " + packs[i].Weight + " - Value " + packs[i].Value);
}
if (packs[i].Weight > remain)
{
i++;
}
if (i == n)
{
stopProc = true;
}
}
Console.WriteLine("Max Value:\t" + result);
}
}
}
Toelichting code:
- Initialiseer het gewicht en de waarde voor elk knapzakpakket.
- Sorteer knapzakpakketten op prijs in aflopende volgorde.
- Als u pakket i.
- Als u het aantal pakketten selecteert, is i voldoende.
- Stop met het bladeren door alle pakketten.
Hier is C#-code om het bovenstaande programma uit te voeren met het eerste voorbeeld:
public void run()
{
/*
* Pack and Weight - Value
*/
int[] W = new int[]{15, 10, 2, 4};
//int[] W = new int[] { 12, 2, 1, 1, 4 };
int[] V = new int[]{30, 25, 2, 6};
//int[] V = new int[] { 4, 2, 1, 2, 10 };
/*
* Max Weight
*/
int M = 37;
//int M = 15;
int n = V.Length;
/*
* Run the algorithm
*/
KnapsackGreProc(W, V, M, n);
}
Je hebt de uitvoer:
Pack 0 - Weight 10 - Value 25 Pack 0 - Weight 10 - Value 25 Pack 0 - Weight 10 - Value 25 Pack 2 - Weight 4 - Value 6 Pack 3 - Weight 2 - Value 2 Max Value: 83
Tegenvoorbeeld van Greedy Three
Het algoritme van Greedy Three lost snel op en kan in sommige gevallen ook optimaal zijn. In sommige speciale gevallen biedt dit echter niet de optimale oplossing. Hier heb je een tegenvoorbeeld:
- De parameters van het probleem zijn: n = 3; M = 10.
- De pakketten: {i = 1; W[ik] = 7; V[ik] = 9; Kosten = 9/7}; {ik = 2; W[ik] = 6; V[i] = 6; Kosten = 1}; {ik = 3; W[ik] = 4; V[ik] = 4; Kosten = 1}.
- Het algoritme selecteert (pakket 1) met een totale waarde van 9, terwijl de optimale oplossing van het probleem (pakket 2, pakket 3) een totale waarde van 10 is.
Hier is Java-code om het bovenstaande programma uit te voeren met het tegenvoorbeeld:
public void run() {
/*
* Pack and Weight - Value
*/
int W[] = new int[]{7, 6, 4};
int V[] = new int[]{9, 6, 4};
/*
* Max Weight
*/
int M = 10;
int n = V.length;
/*
* Run the algorithm
*/
knapsackGreProc(W, V, M, n);
}
Dit is het resultaat:
Pack 0 - Weight 7.0 - Value 9.0 Max Value: 9.0
Dat is alles voor het Fractional Knapsack-probleem.
