Problemă de rucsac fracționat: algoritm lacom cu exemplu
Ce este Greedy Strategy?
Algoritmii greedy sunt ca algoritmii de programare dinamică care sunt adesea folosiți pentru a rezolva probleme optime (găsiți cele mai bune soluții ale problemei în funcție de un anumit criteriu).
Algoritmii greedy implementează selecții locale optime în speranța că acele selecții vor duce la o soluție globală optimă pentru problema de rezolvat. Algoritmii greedy nu sunt adesea prea greu de configurat, rapid (complexitatea timpului este adesea o funcție liniară sau foarte mult o funcție de ordinul doi). În plus, aceste programe nu sunt greu de depanat și folosesc mai puțină memorie. Dar rezultatele nu sunt întotdeauna o soluție optimă.
Strategiile greedy sunt adesea folosite pentru a rezolva problema de optimizare combinatorie prin construirea unei opțiuni A. Opțiunea A este construită prin selectarea fiecărei componente Ai a lui A până la finalizare (suficiente n componente). Pentru fiecare Ai, alegeți Ai în mod optim. În acest fel, este posibil ca la ultimul pas să nu ai nimic de selectat decât să accepți ultima valoare rămasă.
Există două componente critice ale deciziilor lacome:
- Mod de selecție lacomă. Puteți selecta care soluție este cea mai bună în prezent și apoi puteți rezolva subproblema care decurge din efectuarea ultimei selecții. Selectarea algoritmilor lacomi poate depinde de selecțiile anterioare. Dar nu poate depinde de nicio selecție viitoare sau de soluțiile subproblemelor. Algoritmul evoluează într-un mod care face selecții într-o buclă, micșorând în același timp problema dată la subprobleme mai mici.
- Substructură optimă. Efectuați substructura optimă pentru o problemă dacă soluția optimă a acestei probleme conține soluții optime pentru subproblemele sale.
Un algoritm lacom are cinci componente:
- Un set de candidați, din care să creăm soluții.
- O funcție de selecție, pentru a selecta cel mai bun candidat de adăugat la soluție.
- O funcție fezabilă este utilizată pentru a decide dacă un candidat poate fi folosit pentru a construi o soluție.
- O funcție obiectivă, fixând valoarea unei soluții sau a unei soluții incomplete.
- O funcție de evaluare, care indică când găsiți o soluție completă.
Ideea Lacomului
Cu prima idee, aveți următorii pași ai Greedy One:
- Sortați în ordinea non crescătoare a valorilor.
- La rândul său, luați în considerare pachetele comandate, puneți pachetul considerat în rucsac dacă capacitatea rămasă a rucsacului este suficientă pentru a-l conține (ceea ce înseamnă că greutatea totală a pachetelor care au fost introduse în rucsac și greutatea pachetelor considerate nu depășesc capacitatea ghiozdanului).
Cu toate acestea, acest algoritm lacom nu oferă întotdeauna soluția optimă. Aici aveți un contra-exemplu:
- Parametrii problemei sunt: n = 3; M = 19.
- Pachetele: {i = 1; W[i] = 14; V[i] = 20}; {i = 2; W[i] = 6; V[i] = 16}; {i = 3; W[i] = 10; V[i] = 8} -> Valoare mare, dar și greutate mare.
- Algoritmul va selecta pachetul 1 cu o valoare totală de 20, în timp ce soluția optimă a problemei este selectată (pachetul 2, pachetul 3) cu o valoare totală de 24.
Ideea lui Greedy Two
Cu a doua idee, aveți următorii pași ai Greedy Two:
- Sortați în ordinea nedescrescătoare a greutăților.
- La rândul său, luați în considerare pachetele comandate, puneți pachetul considerat în rucsac dacă capacitatea rămasă a rucsacului este suficientă pentru a-l conține (ceea ce înseamnă că greutatea totală a pachetelor care au fost introduse în rucsac și greutatea pachetelor considerate nu depășesc capacitatea ghiozdanului).
Cu toate acestea, acest algoritm lacom nu oferă întotdeauna soluția optimă. Aici aveți un contra-exemplu:
- Parametrii problemei sunt: n = 3; M = 11.
- Pachetele: {i = 1; W[i] = 5; V[i] = 10}; {i = 2; W[i] = 6; V[i] = 16}; {i = 3; W[i] = 10; V[i] = 28} -> Greutate redusă, dar valoarea este și foarte ușoară.
- Algoritmul va selecta (pachetul 1, pachetul 2) cu o valoare totală de 26, în timp ce soluția optimă a problemei este (pachetul 3) cu o valoare totală de 28.
Ideea lui Greedy Three
Cu a treia idee, aveți următorii pași ai lui Greedy Three. De fapt, acesta este cel mai utilizat algoritm.
- Sortați pachetele în ordinea necreșterii valorii costului unitar
. Tu ai:
- La rândul său, luați în considerare pachetele comandate, puneți pachetul considerat în rucsac dacă capacitatea rămasă a rucsacului este suficientă pentru a-l conține (ceea ce înseamnă că greutatea totală a pachetelor care au fost introduse în rucsac și greutatea pachetelor considerate nu depășesc capacitatea ghiozdanului).
Idee: Ideea lacomă a acestei probleme este de a calcula raportul fiecăruia
. Apoi sortați aceste rapoarte în ordine descrescătoare. Vei alege cel mai înalt
pachetul și capacitatea rucsacului poate conține acel pachet (rămâne > wi). De fiecare dată când un pachet este pus în rucsac, acesta va reduce și capacitatea rucsacului.
Modalitate de selectare a pachetelor:
- Luați în considerare gama de costuri unitare. Selectați pachetele în funcție de costurile unitare descrescătoare.
- Să presupunem că ați găsit o soluție parțială: (x1,…, Xi).
- Se obține valoarea rucsacului:
- Corespunzător greutății pachetelor care au fost puse în rucsac:
- Prin urmare, limita de greutate rămasă a rucsacului este:
Etapele algoritmului
Vedeți că aceasta este o problemă de a găsi max. Lista pachetelor este sortată în ordinea descrescătoare a costurilor unitare pentru a lua în considerare ramificarea.
- Etapa 1: Rădăcina nodului reprezintă starea inițială a rucsacului, unde nu ați selectat niciun pachet.
- Valoarea totală = 0.
- Limita superioară a nodului rădăcină UpperBound = M * Costul unitar maxim.
- Etapa 2: Rădăcina nodului va avea noduri secundare corespunzătoare posibilității de a selecta pachetul cu cel mai mare cost unitar. Pentru fiecare nod, recalculați parametrii:
- TotalValue = TotalValue (vechi) + numărul de pachete selectate * valoarea fiecărui pachet.
- M = M (vechi) – numărul de pachete selectate * greutatea fiecărui pachet.
- UpperBound = TotalValue + M (nou) * Costul unitar al pachetului va fi luat în considerare în continuare.
- Etapa 3: În nodurile copil, veți prioritiza ramificarea pentru nodul care are limita superioară mai mare. Copiii acestui nod corespund capacității de a selecta următorul pachet având un cost unitar mare. Pentru fiecare nod, trebuie să recalculați parametrii TotalValue, M, UpperBound conform formulei menționate la pasul 2.
- Etapa 4: Repetați Pasul 3 cu nota: pentru nodurile cu limita superioară este valori mai mici sau egale cu costul maxim temporar al unei opțiuni găsite, nu mai trebuie să vă ramificați pentru acel nod.
- Etapa 5: Dacă toate nodurile sunt ramificate sau tăiate, cea mai scumpă opțiune este cea de căutat.
Pseudocod pentru algoritm:
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
Complexitatea algoritmului:
- Dacă utilizați un algoritm de sortare simplu (selecție, balon...), atunci complexitatea întregii probleme este O(n2).
- Dacă utilizați sortarea rapidă sau sortarea prin îmbinare, atunci complexitatea întregii probleme este O(nlogn).
Java cod pentru Greedy Three
- În primul rând, definiți clasa KnapsackPackage. Această clasă are proprietățile sunt: greutatea, valoarea și costul corespunzător fiecărui pachet. Costul proprietății al acestei clase este utilizat pentru sarcina de sortare în algoritmul principal. Valoarea fiecărui cost este
raportul fiecărui pachet.
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; } }
- Apoi creați o funcție pentru a efectua algoritmul 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); }
Explicația codului:
- Inițializați greutatea și valoarea fiecărui pachet de rucsac.
- Sortați pachetele de rucsac după cost în ordine descrescătoare.
- Dacă selectați pachetul i.
- Dacă selectați numărul de pachet i este suficient.
- Opriți când răsfoiți toate pachetele.
În acest tutorial, aveți două exemple. Iată codul java pentru a rula programul de mai sus cu două exemple:
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); }
Aveți rezultatul:
- Primul exemplu:
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
- Al doilea exemplu:
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
Analizați primul exemplu:
- Parametrii problemei sunt: n = 4; M = 37.
- Pachetele: {i = 1; W[i] = 15; V[i] = 30; Cost = 2.0}; {i = 2; W[i] = 10; V[i] = 25; Cost = 2.5}; {i = 3; W[i] = 2; V[i] = 4; Cost = 1.0}; {i = 4; W[i] = 4; V[i] = 6; Cost = 1.5}.
- Sortați pachetele în ordinea fără creștere a valorii costurilor unitare. Ai: {i = 2} -> {i = 1} -> {i = 4} -> {i = 3}.
Pași pentru aplicarea algoritmului pentru primul exemplu:
- Definiți x1, x2, x3, x4 este numărul fiecărui pachet selectat, corespunzător pachetului {i = 2} -> {i = 1} -> {i = 4} -> {i = 3}.
- Rădăcina nodului N reprezintă starea în care nu ați selectat niciun pachet. Apoi:
- Valoarea totală = 0.
- M = 37 (așa cum s-a propus).
- UpperBound = 37 * 2.5 = 92.5, dintre care 37 este M și 2.5 este costul unitar al pachetului {i = 2}.
- Cu pachetul {i = 2}, ai 4 posibilități: selectează 3 pachete {i = 2} (x1 = 3); selectați 2 pachete {i = 2} (x1 = 2); selectați 1 pachet {i = 2} (x1 = 1) și nu selectați pachetul {i = 2} (x1 = 0). În conformitate cu aceste 4 posibilități, ramificați nodul rădăcină N la 4 copii N[1], N[2], N[3] și N[4].
- Pentru nodul copil N1, aveți:
- TotalValue = 0 + 3 * 25 = 75, unde 3 este numărul pachetului {i = 2} selectat și 25 este valoarea fiecărui pachet {i = 2}.
- M = 37 – 3 * 10 = 7, unde 37 este cantitatea inițială a rucsacului, 3 este numărul de pachete {i = 2}, 10 este greutatea fiecărui pachet {i = 2}.
- UpperBound = 75 + 7 * 2 = 89, unde 75 este TotalValue, 7 este greutatea rămasă a rucsacului și 2 este costul unitar al pachetului {i = 1}.
- În mod similar, puteți calcula parametrii pentru nodurile N[2], N[3] și N[4], în care UpperBound este 84, 79 și, respectiv, 74.
- Printre nodurile N[1], N[2], N[3] și N[4], nodul N[1] are cea mai mare Limită superioară, așa că veți ramifica mai întâi nodul N[1] în speranța că va exista o plan bun din aceasta directie.
- Din nodul N[1], aveți un singur nod copil N[1-1] corespunzător lui x2 = 0 (datorită greutății rămase a rucsacului este 7, în timp ce greutatea fiecărui pachet {i = 1} este 15) . După determinarea parametrilor pentru butonul N[1-1], aveți UpperBound of N[1-1] 85.5.
- Continuați să ramificați nodul N[1-1]. Nodul N[1-1] are 2 copii N[1-1-1] și N[1-1-2] corespunzători lui x3 = 1 și x3 = 0. După determinarea parametrilor pentru aceste două noduri, vedeți că Limita superioară a lui N[1-1-1] este 84 și cea a lui N[1-1-2] este 82, așa că continuați să ramificați nodul N[1-1-1].
- Nodul N[1-1-1] are doi copii, N[1-1-1-1] și N[1-1-1-2], corespunzător lui x4 = 1 și x4 = 0. Acestea sunt două noduri frunze. (reprezentând opțiunea) deoarece pentru fiecare nod a fost selectat numărul de pachete. În care nodul N[1-1-1-1] reprezintă opțiunea x1 = 3, x2 = 0, x3 = 1 și x4 = 1 pentru 83, în timp ce nodul N[1-1-1-2] reprezintă opțiunea x1 = 3, x2 = 0, x3 = 1 și x4 = 01 la 81. Deci valoarea maximă temporară aici este 83.
- Revenind la nodul N[1-1-2], vedeți că Limita superioară a lui N[1-1-2] este 82 < 83, așa că tăiați nodul N[1-1-2].
- Revenind la nodul N2, vedeți că Limita superioară a lui N2 este 84 > 83, așa că continuați să ramificați nodul N2. Nodul N2 are doi copii N[2-1] și N[2-2] corespunzători lui x2 = 1 și x2 = 0. După calcularea parametrilor pentru N[2-1] și N[2-2], vedeți Limita superioară a lui N[2-1] este 83 și cea a lui N[2-2] este 75.25. Niciuna dintre aceste valori nu este mai mare de 83, așa că ambele noduri sunt tăiate.
- În cele din urmă, nodurile N3 și N4 sunt de asemenea tăiate.
- Deci toate nodurile de pe copac sunt ramificate sau tăiate, astfel încât cea mai bună soluție temporară este cea pe care o căutați. În consecință, trebuie să selectați 3 pachete {i = 2}, 1 pachet {i = 4} și un pachet {i = 3} cu o valoare totală de 83, greutatea totală este de 36.
Cu aceeași analiză a celui de-al doilea exemplu, aveți rezultatul: selectați pachetul 4 (de 3 ori) și pachetul 5 (de 3 ori).
Python3 cod pentru Greedy Three
- În primul rând, definiți clasa 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
- Apoi creați o funcție pentru a efectua algoritmul 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)
Explicația codului:
- Inițializați greutatea și valoarea fiecărui pachet de rucsac.
- Sortați pachetele de rucsac după cost în ordine descrescătoare.
- Dacă selectați pachetul i.
- Dacă selectați numărul de pachet i este suficient.
- Opriți când răsfoiți toate pachetele.
Aici este Python3 pentru a rula programul de mai sus cu primul exemplu:
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)
Aveți rezultatul:
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
Cod C# pentru Greedy Three
- În primul rând, definiți clasa 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; } } } }
- Apoi creați o funcție pentru a efectua algoritmul 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); } } }
Explicația codului:
- Inițializați greutatea și valoarea fiecărui pachet de rucsac.
- Sortați pachetele de rucsac după cost în ordine descrescătoare.
- Dacă selectați pachetul i.
- Dacă selectați numărul de pachet i este suficient.
- Opriți când răsfoiți toate pachetele.
Iată codul C# pentru a rula programul de mai sus cu primul exemplu:
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); }
Aveți rezultatul:
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
Contra-exemplu pentru Greedy Three
Algoritmul lui Greedy Three se rezolvă rapid și poate fi, de asemenea, optim în unele cazuri. Cu toate acestea, în unele cazuri speciale, nu oferă soluția optimă. Aici aveți un contra-exemplu:
- Parametrii problemei sunt: n = 3; M = 10.
- Pachetele: {i = 1; W[i] = 7; V[i] = 9; Cost = 9/7}; {i = 2; W[i] = 6; V[i] = 6; Cost = 1}; {i = 3; W[i] = 4; V[i] = 4; Cost = 1}.
- Algoritmul va selecta (pachetul 1) cu o valoare totală de 9, în timp ce soluția optimă a problemei este (pachetul 2, pachetul 3) cu o valoare totală de 10.
Iată codul java pentru a rula programul de mai sus cu contra-exemplul:
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); }
Iată rezultatul:
Pack 0 - Weight 7.0 - Value 9.0 Max Value: 9.0
Asta e tot pentru problema Fractional Knapsack.