Fractional Napsack Problem: Grådig algoritme med eksempel
Sarah Chen
Hvad er Greedy Strategy?
Grådige algoritmer er som dynamiske programmeringsalgoritmer, der ofte bruges til at løse optimale problemer (find bedste løsninger på problemet efter et bestemt kriterium).
Grådige algoritmer implementerer optimale lokale valg i håb om, at disse valg vil føre til en optimal global løsning på problemet, der skal løses. Grådige algoritmer er ofte ikke for svære at sætte op, hurtige (tidskompleksitet er ofte en lineær funktion eller meget en andenordens funktion). Desuden er disse programmer ikke svære at fejlfinde og bruger mindre hukommelse. Men resultaterne er ikke altid en optimal løsning.
Grådige strategier bruges ofte til at løse det kombinatoriske optimeringsproblem ved at bygge en mulighed A. Mulighed A konstrueres ved at vælge hver komponent Ai i A, indtil den er færdig (nok n komponenter). For hver Ai vælger du Ai optimalt. På denne måde er det muligt, at du på det sidste trin ikke har andet at vælge end at acceptere den sidste resterende værdi.
Der er to kritiske komponenter i grådige beslutninger:
- Vejen til grådig udvælgelse. Du kan vælge, hvilken løsning der er bedst på nuværende tidspunkt og derefter løse det delproblem, der opstår ved at foretage det sidste valg. Valget af grådige algoritmer kan afhænge af tidligere valg. Men det kan ikke afhænge af nogen fremtidig udvælgelse eller afhængig af løsningerne af delproblemer. Algoritmen udvikler sig på en måde, der foretager valg i en løkke, samtidig med at den givne problemstilling formindskes til mindre delproblemer.
- Optimal underbygning. Du udfører den optimale understruktur for et problem, hvis den optimale løsning af dette problem indeholder optimale løsninger på dets underproblemer.
En grådig algoritme har fem komponenter:
- Et sæt af kandidater, hvorfra man kan skabe løsninger.
- En udvælgelsesfunktion, til at vælge den bedste kandidat til at tilføje til løsningen.
- En gennemførlig funktion bruges til at afgøre, om en kandidat kan bruges til at bygge en løsning.
- En objektiv funktion, der fastsætter værdien af en løsning eller en ufuldstændig løsning.
- En evalueringsfunktion, der angiver, hvornår du finder en komplet løsning.
Idéen om Greedy One
Med den første idé har du følgende trin i Greedy One:
- Sorter i ikke-stigende rækkefølge af værdier.
- Overvej til gengæld de bestilte pakker, læg den overvejende pakke i rygsækken, hvis den resterende kapacitet af rygsækken er nok til at indeholde den (hvilket betyder, at den samlede vægt af de pakker, der er lagt i rygsækken og vægten af de overvejende pakker, ikke overstiger rygsækkens kapacitet).
Denne grådige algoritme giver dog ikke altid den optimale løsning. Her har du et modeksempel:
- Parametrene for problemet er: n = 3; M = 19.
- Pakkerne: {i = 1; W[i] = 14; V[i] = 20}; {i = 2; W[i] = 6; V[i] = 16}; {i = 3; W[i] = 10; V[i] = 8} -> Stor værdi, men også stor vægt.
- Algoritmen vil vælge pakke 1 med en samlet værdi på 20, mens den optimale løsning af problemet vælges (pakke 2, pakke 3) med en samlet værdi på 24.
Idéen om Greedy Two
Med den anden idé har du følgende trin i Greedy Two:
- Sorter i ikke-faldende rækkefølge af vægte.
- Overvej til gengæld de bestilte pakker, læg den overvejende pakke i rygsækken, hvis den resterende kapacitet af rygsækken er nok til at indeholde den (hvilket betyder, at den samlede vægt af de pakker, der er lagt i rygsækken og vægten af de overvejende pakker, ikke overstiger rygsækkens kapacitet).
Denne grådige algoritme giver dog ikke altid den optimale løsning. Her har du et modeksempel:
- Parametrene for problemet er: n = 3; M = 11.
- Pakkerne: {i = 1; W[i] = 5; V[i] = 10}; {i = 2; W[i] = 6; V[i] = 16}; {i = 3; W[i] = 10; V[i] = 28} -> Let vægt, men værdien er også meget lav.
- Algoritmen vil vælge (pakke 1, pakke 2) med en samlet værdi på 26, mens den optimale løsning af problemet er (pakke 3) med en samlet værdi på 28.
Idéen om Greedy Three
Med den tredje idé har du følgende trin i Greedy Three. Faktisk er dette den mest udbredte algoritme.
- Sorter pakker i den rækkefølge, hvor værdien af enhedsomkostninger ikke stiger
. Du har:
- Overvej til gengæld de bestilte pakker, læg den overvejende pakke i rygsækken, hvis den resterende kapacitet af rygsækken er nok til at indeholde den (hvilket betyder, at den samlede vægt af de pakker, der er lagt i rygsækken og vægten af de overvejende pakker, ikke overstiger rygsækkens kapacitet).
Idea: Den grådige idé med det problem er at beregne 
forholdet mellem hver 
. Sorter derefter disse forhold i faldende rækkefølge. Du vil vælge den højeste pakken og rygsækkens kapacitet kan indeholde denne pakke (rest > wi). Hver gang en pakke lægges i rygsækken, vil det også reducere rygsækkens kapacitet.
Måde at vælge pakkerne på:
- Overvej rækken af enhedsomkostninger. Du vælger pakker efter faldende enhedsomkostninger.
- Antag, at du fandt en delvis løsning: (x1,…, Xi).
- Rygsækkens værdi opnås:
- Svarende til vægten af pakker, der er lagt i rygsækken:
- Derfor er den resterende vægtgrænse for rygsækken:
Algoritme trin
Du kan se, at dette er et problem med at finde max. Listen over pakker er sorteret i faldende rækkefølge af enhedsomkostninger for at overveje forgrening.
- Trin 1: Noderod repræsenterer rygsækkens starttilstand, hvor du ikke har valgt nogen pakke.
- Samlet værdi = 0.
- Den øvre grænse for rodknuden UpperBound = M * Maksimal enhedsomkostning.
- Trin 2: Noderod vil have underordnede noder svarende til muligheden for at vælge pakken med den største enhedspris. For hver node genberegner du parametrene:
- TotalValue = TotalValue (gammel) + antal valgte pakker * værdi af hver pakke.
- M = M (gammel) – antal valgte pakker * vægt af hver pakke.
- UpperBound = TotalValue + M (ny) * Enhedsprisen for den pakke, der skal overvejes næste gang.
- Trin 3: I underordnede noder vil du prioritere forgrening for den node, der har den større øvre grænse. Børnene i denne node svarer til evnen til at vælge den næste pakke med store enhedsomkostninger. For hver node skal du genberegne parametrene TotalValue, M, UpperBound i henhold til formlen nævnt i trin 2.
- Trin 4: Gentag trin 3 med bemærkningen: for noder med øvre grænse er lavere eller lig med den midlertidige maksimale pris for en fundet mulighed, behøver du ikke at forgrene for den node længere.
- Trin 5: Hvis alle noder er forgrenede eller afskåret, er den dyreste mulighed den, du skal kigge efter.
Pseudokode for algoritmen:
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
Kompleksiteten af algoritmen:
- Hvis du bruger en simpel sorteringsalgoritme (selektion, boble...), så er kompleksiteten af hele problemet O(n2).
- Hvis du bruger hurtig sortering eller flette sortering, så er kompleksiteten af hele problemet O(nlogn).
Java kode til Greedy Three
- For det første definerer du klasse KnapsackPackage. Denne klasse har egenskaber: vægt, værdi og tilsvarende pris for hver pakke. Ejendomsomkostningerne for denne klasse bruges til at sortere opgave i hovedalgoritmen. Værdien af hver omkostning er
forholdet mellem hver pakke.
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;
}
}
- Du opretter derefter en funktion til at udføre algoritmen Greedy Three.
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);
}
Forklaring af kode:
- Initialiser vægt og værdi for hver rygsækpakke.
- Sorter rygsækpakker efter pris i faldende rækkefølge.
- Hvis du vælger pakke i.
- Hvis vælge antallet af pakke i er nok.
- Stop, når du gennemser alle pakker.
I denne tutorial har du to eksempler. Her er java-kode til at køre ovenstående program med to eksempler:
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);
}
Du har output:
- Første eksempel:
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
- Andet eksempel:
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
Analyser det første eksempel:
- Parametrene for problemet er: n = 4; M = 37.
- Pakkerne: {i = 1; W[i] = 15; V[i] = 30; Pris = 2.0}; {i = 2; W[i] = 10; V[i] = 25; Pris = 2.5}; {i = 3; W[i] = 2; V[i] = 4; Pris = 1.0}; {i = 4; W[i] = 4; V[i] = 6; Pris = 1.5}.
- Du sorterer pakker i den rækkefølge, hvor værdien af enhedsomkostningerne ikke stiger. Du har: {i = 2} -> {i = 1} -> {i = 4} -> {i = 3}.
Trin til anvendelse af algoritme for det første eksempel:
- Definer x1, x2, x3, x4 er nummeret på hver valgt pakke, svarende til pakke {i = 2} -> {i = 1} -> {i = 4} -> {i = 3}.
- Noderod N repræsenterer tilstanden, hvor du ikke har valgt nogen pakke. Derefter:
- Samlet værdi = 0.
- M = 37 (som foreslået).
- UpperBound = 37 * 2.5 = 92.5, hvoraf 37 er M og 2.5 er enhedsprisen for pakken {i = 2}.
- Med pakke {i = 2} har du 4 muligheder: vælg 3 pakker {i = 2} (x1 = 3); vælg 2 pakker {i = 2} (x1 = 2); vælg 1 pakke {i = 2} (x1 = 1) og ikke vælg pakke {i = 2} (x1 = 0). I overensstemmelse med disse 4 muligheder forgrener du rodnoden N til 4 børn N[1], N[2], N[3] og N[4].
- For underordnet node N1 har du:
- TotalVærdi = 0 + 3 * 25 = 75, hvor 3 er antallet af valgte pakke {i = 2}, og 25 er værdien af hver pakke {i = 2}.
- M = 37 – 3 * 10 = 7, hvor 37 er den oprindelige mængde af rygsækken, 3 er antallet af pakker {i = 2}, 10 er vægten af hver pakke {i = 2}.
- UpperBound = 75 + 7 * 2 = 89, hvor 75 er TotalVærdi, 7 er den resterende vægt af rygsækken og 2 er enhedsprisen for pakken {i = 1}.
- På samme måde kan du beregne parametrene for noderne N[2], N[3] og N[4], hvor UpperBound er henholdsvis 84, 79 og 74.
- Blandt noderne N[1], N[2], N[3] og N[4] har node N[1] den største UpperBound, så du forgrener node N[1] først i håbet om, at der vil være en god plan fra denne retning.
- Fra node N[1] har du kun én underordnet node N[1-1] svarende til x2 = 0 (på grund af den resterende vægt af rygsækken er 7, mens vægten af hver pakke {i = 1} er 15) . Efter at have bestemt parametrene for N[1-1]-knappen, har du den øvre grænse for N[1-1] 85.5.
- Du fortsætter med at forgrene node N[1-1]. Node N[1-1] har 2 børn N[1-1-1] og N[1-1-2] svarende til x3 = 1 og x3 = 0. Efter at have bestemt parametrene for disse to noder, ser man, at Den øvre grænse for N[1-1-1] er 84, og den for N[1-1-2] er 82, så du fortsætter med at forgrene node N[1-1-1].
- Node N[1-1-1] har to børn, N[1-1-1-1] og N[1-1-1-2], svarende til x4 = 1 og x4 = 0. Disse er to bladknuder (repræsenterer muligheden), fordi antallet af pakker er valgt for hver node. I hvilken node N[1-1-1-1] repræsenterer muligheden x1 = 3, x2 = 0, x3 = 1 og x4 = 1 for 83, mens node N[1-1-1-2] repræsenterer muligheden x1 = 3, x2 = 0, x3 = 1 og x4 = 01 ved 81. Så den midlertidige maksimumværdi her er 83.
- Hvis du vender tilbage til node N[1-1-2], ser du, at den øvre grænse for N[1-1-2] er 82 < 83, så du trimmer node N[1-1-2].
- Når du vender tilbage til node N2, ser du, at den øvre grænse for N2 er 84 > 83, så du fortsætter med at forgrene node N2. Noden N2 har to børn N[2-1] og N[2-2] svarende til x2 = 1 og x2 = 0. Efter at have beregnet parametrene for N[2-1] og N[2-2], ser du den øvre grænse for N[2-1] er 83, og den for N[2-2] er 75.25. Ingen af disse værdier er større end 83, så begge noder trimmes.
- Endelig trimmes også knudepunkter N3 og N4.
- Så alle knuderne på træet er forgrenede eller trimmede, så den bedste midlertidige løsning er den, du skal kigge efter. Derfor skal du vælge 3 pakker {i = 2}, 1 pakke {i = 4} og en pakke {i = 3} med en samlet værdi på 83, samlet vægt er 36.
Med samme analyse af det andet eksempel har du resultatet: vælg pakke 4 (3 gange) og pakke 5 (3 gange).
Python3-kode til Greedy Three
- For det første definerer du 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
- Du opretter derefter en funktion til at udføre algoritmen Greedy Three.
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)
Forklaring af kode:
- Initialiser vægt og værdi for hver rygsækpakke.
- Sorter rygsækpakker efter pris i faldende rækkefølge.
- Hvis du vælger pakke i.
- Hvis vælge antallet af pakke i er nok.
- Stop, når du gennemser alle pakker.
Her er Python3 kode for at køre ovenstående program med det første eksempel:
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)
Du har output:
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#-kode til Greedy Three
- For det første definerer du 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; }
}
}
}
- Du opretter derefter en funktion til at udføre algoritmen Greedy Three.
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);
}
}
}
Forklaring af kode:
- Initialiser vægt og værdi for hver rygsækpakke.
- Sorter rygsækpakker efter pris i faldende rækkefølge.
- Hvis du vælger pakke i.
- Hvis vælge antallet af pakke i er nok.
- Stop, når du gennemser alle pakker.
Her er C#-kode til at køre ovenstående program med det første eksempel:
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);
}
Du har output:
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
Modeksempel på Greedy Three
Algoritmen for Greedy Three løses hurtigt og kan også være optimal i nogle tilfælde. I nogle særlige tilfælde giver det dog ikke den optimale løsning. Her har du et modeksempel:
- Parametrene for problemet er: n = 3; M = 10.
- Pakkerne: {i = 1; W[i] = 7; V[i] = 9; Pris = 9/7}; {i = 2; W[i] = 6; V[i] = 6; Pris = 1}; {i = 3; W[i] = 4; V[i] = 4; Pris = 1}.
- Algoritmen vil vælge (pakke 1) med en samlet værdi på 9, mens den optimale løsning af problemet er (pakke 2, pakke 3) med en samlet værdi på 10.
Her er java-kode til at køre ovenstående program med modeksemplet:
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);
}
Her er resultatet:
Pack 0 - Weight 7.0 - Value 9.0 Max Value: 9.0
Det er alt til Fractional Napsack-problemet.