Tört hátizsák probléma: Mohó algoritmus példával
Sarah Chen
Mi az a mohó stratégia?
A mohó algoritmusok olyanok, mint a dinamikus programozási algoritmusok, amelyeket gyakran az optimális problémák megoldására használnak (a probléma legjobb megoldásainak megtalálása egy adott kritérium szerint).
A mohó algoritmusok optimális helyi kijelöléseket valósítanak meg abban a reményben, hogy ezek a kijelölések a megoldandó probléma optimális globális megoldásához vezetnek. A mohó algoritmusokat gyakran nem túl nehéz beállítani, gyorsak (az időbonyolultság gyakran lineáris függvény vagy nagyon is másodrendű függvény). Ezenkívül ezeket a programokat nem nehéz hibakeresni, és kevesebb memóriát használnak. De az eredmények nem mindig jelentik az optimális megoldást.
A mohó stratégiákat gyakran alkalmazzák a kombinatorikus optimalizációs probléma megoldására egy A opció felépítésével. Az A opciót úgy állítják össze, hogy az A minden egyes Ai komponensét kijelölik, amíg az elkészül (elég n komponens). Minden Ai-hez optimálisan választja az Ai-t. Ily módon előfordulhat, hogy az utolsó lépésben nem kell mást választania, mint elfogadni az utolsó megmaradt értéket.
A mohó döntéseknek két kritikus összetevője van:
- A mohó kiválasztás módja. Kiválaszthatja, hogy jelenleg melyik megoldás a legjobb, majd megoldhatja az utolsó kiválasztás során felmerülő részproblémát. A mohó algoritmusok kiválasztása a korábbi kiválasztásoktól függhet. De ez nem függhet semmilyen jövőbeli kiválasztástól vagy részproblémák megoldásától. Az algoritmus úgy fejlődik, hogy ciklusban választja ki, ugyanakkor az adott problémát kisebb részproblémákká zsugorítja.
- Optimális alépítmény. Egy probléma optimális alstruktúráját akkor hajtja végre, ha ennek a feladatnak az optimális megoldása tartalmazza a részproblémák optimális megoldásait.
Egy mohó algoritmusnak öt összetevője van:
- Jelöltek halmaza, amelyekből megoldásokat lehet alkotni.
- Kiválasztási funkció a megoldáshoz a legjobb jelölt kiválasztásához.
- Egy megvalósítható függvényt használnak annak eldöntésére, hogy egy jelölt felhasználható-e megoldás felépítésére.
- Célfüggvény, amely egy megoldás vagy egy hiányos megoldás értékét rögzíti.
- Értékelő funkció, amely jelzi, ha teljes megoldást talál.
A Mohó Egy ötlete
Az első ötlettel a Greedy One következő lépései vannak:
- Rendezés az értékek nem növekvő sorrendjében.
- A megrendelt csomagokat viszont mérlegelje, a mérlegelési csomagot hátizsákba tegye, ha a hátizsák fennmaradó kapacitása elegendő annak befogadására (ami azt jelenti, hogy a hátizsákba helyezett csomagok össztömege és a figyelembe vett csomagok tömege nem haladja meg a a hátizsák kapacitása).
Ez a mohó algoritmus azonban nem mindig adja meg az optimális megoldást. Itt van egy ellenpélda:
- A feladat paraméterei: n = 3; M = 19.
- A csomagok: {i = 1; W[i] = 14; V[i] = 20}; {i = 2; W[i] = 6; V[i] = 16}; {i = 3; W[i] = 10; V[i] = 8} -> Nagy érték, de nagy súly is.
- Az algoritmus az 1-es csomagot 20-as összértékű, míg a feladat optimális megoldását (2-es csomag, 3-as csomag) 24-es összértékkel választja ki.
A Mohó Kettő ötlete
A második ötlettel a Greedy Two következő lépései vannak:
- Rendezés a súlyok nem csökkenő sorrendjében.
- A megrendelt csomagokat viszont mérlegelje, a mérlegelési csomagot hátizsákba tegye, ha a hátizsák fennmaradó kapacitása elegendő annak befogadására (ami azt jelenti, hogy a hátizsákba helyezett csomagok össztömege és a figyelembe vett csomagok tömege nem haladja meg a a hátizsák kapacitása).
Ez a mohó algoritmus azonban nem mindig adja meg az optimális megoldást. Itt van egy ellenpélda:
- A feladat paraméterei: n = 3; M = 11.
- A csomagok: {i = 1; W[i] = 5; V[i] = 10}; {i = 2; W[i] = 6; V[i] = 16}; {i = 3; W[i] = 10; V[i] = 28} -> Könnyű, de az értéke is nagyon könnyű.
- Az algoritmus (1. csomag, 2. csomag) 26-os összértéket választ, míg a feladat optimális megoldása (3. csomag) 28-as összértékkel.
A Mohó Három ötlete
A harmadik ötlettel a Greedy Three következő lépései vannak. Valójában ez a legszélesebb körben használt algoritmus.
- A csomagokat az egységköltség értékének nem növekedése szerinti sorrendben rendezze
. Neked van:
- A megrendelt csomagokat viszont mérlegelje, a mérlegelési csomagot hátizsákba tegye, ha a hátizsák fennmaradó kapacitása elegendő annak befogadására (ami azt jelenti, hogy a hátizsákba helyezett csomagok össztömege és a figyelembe vett csomagok tömege nem haladja meg a a hátizsák kapacitása).
Ötlet: A probléma mohó ötlete az, hogy kiszámítsuk a 
mindegyik aránya 
. Ezután rendezze ezeket az arányokat csökkenő sorrendben. A legmagasabbat fogja választani csomag és a hátizsák kapacitása tartalmazhatja azt a csomagot (maradvány > wi). Minden alkalommal, amikor egy csomagot a hátizsákba tesznek, az a hátizsák kapacitását is csökkenti.
A csomagok kiválasztásának módja:
- Tekintsük az egységköltségek tömbjét. Csomagokat a csökkenő egységköltségek szerint választja ki.
- Tegyük fel, hogy talált egy részmegoldást: (x1,…, Xi).
- A hátizsák értékét megkapjuk:
- A hátizsákba helyezett csomagok súlyának megfelelően:
- Ezért a hátizsák fennmaradó súlyhatára:
Az algoritmus lépései
Látod, ez a probléma a max. A csomagok listája az egységköltségek csökkenő sorrendjében van rendezve, hogy fontolóra vegye az elágazást.
- 1 lépés: A csomópont gyökér a hátizsák kezdeti állapotát jelenti, ahol nem választott ki egyetlen csomagot sem.
- TotalValue = 0.
- A gyökércsomópont felső határa UpperBound = M * Maximális egységköltség.
- 2 lépés: A csomópontgyökér lesz a gyermek csomópontok, amelyek megfelelnek a legnagyobb egységköltségű csomag kiválasztásának képességének. Minden csomópontnál újra kell számítani a paramétereket:
- TotalValue = TotalValue (régi) + a kiválasztott csomagok száma * minden csomag értéke.
- M = M (régi) – a kiválasztott csomagok száma * minden csomag súlya.
- UpperBound = TotalValue + M (új) * A következőként figyelembe veendő csomag egységköltsége.
- 3 lépés: Az utódcsomópontokban a nagyobb felső korláttal rendelkező csomópont elágazását részesíti előnyben. Ennek a csomópontnak a gyermekei megfelelnek a következő nagy egységköltségű csomag kiválasztásának képességének. Minden csomópontnál újra kell számítani a TotalValue, M, UpperBound paramétereket a 2. lépésben említett képlet szerint.
- 4 lépés: Ismételje meg a 3. lépést azzal a megjegyzéssel: ha a felső határérték kisebb vagy egyenlő egy talált opció ideiglenes maximális költségével, akkor többé nem kell elágaznia az adott csomóponthoz.
- 5 lépés: Ha minden csomópont elágazó vagy levágott, akkor a legdrágább megoldás az, amelyet keresni kell.
Az algoritmus pszeudo kódja:
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
Az algoritmus összetettsége:
- Ha egy egyszerű rendezési algoritmust használunk (kijelölés, buborék…), akkor az egész probléma összetettsége O(n2).
- Ha gyors rendezést vagy összevonási rendezést használ, akkor az egész probléma összetettsége O(nlogn).
Java a Greedy Three kódja
- Először is meg kell határoznia a KnapsackPackage osztályt. Ennek az osztálynak a következő tulajdonságai vannak: minden csomag súlya, értéke és megfelelő költsége. Ennek az osztálynak az ingatlanköltsége a fő algoritmusban a rendezési feladathoz használatos. Az egyes költségek értéke a
az egyes csomagok aránya.
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;
}
}
- Ezután létrehoz egy függvényt a Greedy Three algoritmus végrehajtásához.
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);
}
A kód magyarázata:
- Minden hátizsák-csomag súlyát és értékét inicializálja.
- Válogassa szét a hátizsákcsomagokat költség szerint, csökkenő sorrendben.
- Ha az i. csomagot választja.
- Ha kiválasztja a csomagok számát, az i elég.
- Állítsa le az összes csomag böngészésekor.
Ebben az oktatóanyagban két példa van. Íme a java kód a fenti program futtatásához, két példával:
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);
}
Megvan a kimenet:
- Első példa:
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
- Második példa:
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
Elemezze az első példát:
- A feladat paraméterei: n = 4; M = 37.
- A csomagok: {i = 1; W[i] = 15; V[i] = 30; Költség = 2.0}; {i = 2; W[i] = 10; V[i] = 25; Költség = 2.5}; {i = 3; W[i] = 2; V[i] = 4; Költség = 1.0}; {i = 4; W[i] = 4; V[i] = 6; Költség = 1.5}.
- A csomagokat a fajlagos költségek értékének növekedése szerinti sorrendbe rendezi. Önnek van: {i = 2} -> {i = 1} -> {i = 4} -> {i = 3}.
Az első példa algoritmusának alkalmazásának lépései:
- Határozza meg az x1, x2, x3, x4 az egyes kiválasztott csomagok számát, amelyek megfelelnek az {i = 2} csomagnak -> {i = 1} -> {i = 4} -> {i = 3}.
- Az N csomópont gyökér azt az állapotot jelöli, hogy nem választott ki egyetlen csomagot sem. Akkor:
- TotalValue = 0.
- M = 37 (a javaslat szerint).
- UpperBound = 37 * 2.5 = 92.5, ebből 37 M, 2.5 pedig az {i = 2} csomag egységköltsége.
- Az {i = 2} csomaggal 4 lehetőséged van: válassz 3 csomagot {i = 2} (x1 = 3); válasszon 2 csomagot {i = 2} (x1 = 2); válasszon 1 csomagot {i = 2} (x1 = 1), és ne válassza ki az {i = 2} csomagot (x1 = 0). Ennek a 4 lehetőségnek megfelelően az N gyökércsomópontot leágazza 4 gyermekre: N[1], N[2], N[3] és N[4].
- Az N1 gyermekcsomóponthoz a következőkre van szüksége:
- TotalValue = 0 + 3 * 25 = 75, ahol 3 a kiválasztott {i = 2} csomag száma, és 25 az egyes csomagok {i = 2} értéke.
- M = 37 – 3 * 10 = 7, ahol 37 a hátizsák kezdeti mennyisége, 3 a csomagok száma {i = 2}, 10 az egyes csomagok súlya {i = 2}.
- UpperBound = 75 + 7 * 2 = 89, ahol 75 a TotalValue, 7 a hátizsák fennmaradó súlya és 2 a csomag egységköltsége {i = 1}.
- Hasonlóképpen kiszámíthatja az N[2], N[3] és N[4] csomópontok paramétereit, amelyekben a felső határ 84, 79 és 74.
- Az N[1], N[2], N[3] és N[4] csomópontok közül az N[1] csomópont rendelkezik a legnagyobb felső határral, így először az N[1] csomópontot kell elágazni abban a reményben, hogy lesz egy jó terv ebből az irányból.
- Az N[1] csomópontból csak egy N[1-1] gyermekcsomópontja van, amely x2 = 0-nak felel meg (a hátizsák fennmaradó súlya miatt 7, míg az egyes csomagok súlya {i = 1} 15) . Az N[1-1] gomb paramétereinek meghatározása után az N[1-1] felső határa 85.5.
- Folytatja az N[1-1] csomópont elágazását. Az N[1-1] csomópontnak 2 gyermeke van: N[1-1-1] és N[1-1-2], amelyek x3 = 1 és x3 = 0 értéknek felelnek meg. A két csomópont paramétereinek meghatározása után láthatja, hogy a Az N[1-1-1] felső határa 84, az N[1-1-2]é pedig 82, tehát folytatja az N[1-1-1] csomópont elágazását.
- Az N[1-1-1] csomópontnak két gyermeke van, N[1-1-1-1] és N[1-1-1-2], amelyek megfelelnek x4 = 1 és x4 = 0. Ez két levélcsomópont (az opciót jelenti), mert minden csomóponthoz a csomagok száma lett kiválasztva. Amelyben az N[1-1-1-1] csomópont az x1 = 3, x2 = 0, x3 = 1 és x4 = 1 opciót jelöli 83 esetén, míg az N[1-1-1-2] csomópont az x1 opciót = 3, x2 = 0, x3 = 1 és x4 = 01 81-nél. Tehát az ideiglenes maximális érték itt 83.
- Ha visszakanyarodunk az N[1-1-2] csomóponthoz, azt látjuk, hogy az N[1-1-2] felső határa 82 < 83, tehát levágja az N[1-1-2] csomópontot.
- Visszatérve az N2 csomóponthoz, azt látja, hogy az N2 felső határa 84 > 83, tehát folytatja az N2 csomópont elágazását. Az N2 csomópontnak két gyermeke van: N[2-1] és N[2-2], amelyek x2 = 1 és x2 = 0. Az N[2-1] és N[2-2] paraméterek kiszámítása után látni fogjuk, hogy az N[2-1] felső határa 83, az N[2-2]-é pedig 75.25. Ezen értékek egyike sem nagyobb 83-nál, így mindkét csomópont le van vágva.
- Végül az N3 és N4 csomópontokat is levágjuk.
- Tehát a fa összes csomópontja elágazó vagy levágott, így a legjobb ideiglenes megoldás az, amelyet keresni kell. Ennek megfelelően ki kell választani 3 csomagot {i = 2}, 1 csomagot {i = 4} és egy csomagot {i = 3}, amelyek összértéke 83, össztömege 36.
A második példa azonos elemzésével megvan az eredmény: válassza ki a 4-es csomagot (3-szor) és az 5-ös csomagot (3-szor).
Python3 kód a Greedy Three-hez
- Először is meg kell határoznia a KnapsackPackage osztályt.
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
- Ezután létrehoz egy függvényt a Greedy Three algoritmus végrehajtásához.
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)
A kód magyarázata:
- Minden hátizsák-csomag súlyát és értékét inicializálja.
- Válogassa szét a hátizsákcsomagokat költség szerint, csökkenő sorrendben.
- Ha az i. csomagot választja.
- Ha kiválasztja a csomagok számát, az i elég.
- Állítsa le az összes csomag böngészésekor.
Itt van Python3 kód a fenti program futtatásához az első példával:
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)
Megvan a kimenet:
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# kód a Greedy Three számára
- Először is meg kell határoznia a KnapsackPackage osztályt.
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; }
}
}
}
- Ezután létrehoz egy függvényt a Greedy Three algoritmus végrehajtásához.
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);
}
}
}
A kód magyarázata:
- Minden hátizsák-csomag súlyát és értékét inicializálja.
- Válogassa szét a hátizsákcsomagokat költség szerint, csökkenő sorrendben.
- Ha az i. csomagot választja.
- Ha kiválasztja a csomagok számát, az i elég.
- Állítsa le az összes csomag böngészésekor.
Itt található a C# kód a fenti program futtatásához az első példával:
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);
}
Megvan a kimenet:
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
Ellenpélda a Kapzsi Háromra
A Greedy Three algoritmusa gyorsan megoldódik, és bizonyos esetekben optimális is lehet. Egyes speciális esetekben azonban nem ad optimális megoldást. Itt van egy ellenpélda:
- A feladat paraméterei: n = 3; M = 10.
- A csomagok: {i = 1; W[i] = 7; V[i] = 9; Költség = 9/7}; {i = 2; W[i] = 6; V[i] = 6; Költség = 1}; {i = 3; W[i] = 4; V[i] = 4; Költség = 1}.
- Az algoritmus (1. csomag) 9-es összértékkel választja ki, míg a feladat optimális megoldása (2. csomag, 3. csomag) 10-es összértékkel.
Itt van a java kód a fenti program futtatásához az ellenpéldával:
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);
}
Itt van az eredmény:
Pack 0 - Weight 7.0 - Value 9.0 Max Value: 9.0
Ennyi a frakcionált hátizsák problémája.
