Problema dello zaino frazionario: algoritmo Greedy con esempio
Sara Chen
Cos'è la strategia golosa?
Gli algoritmi greedy sono come algoritmi di programmazione dinamica che vengono spesso utilizzati per risolvere problemi ottimali (trovare le migliori soluzioni del problema secondo un criterio particolare).
Gli algoritmi greedy implementano selezioni locali ottimali nella speranza che tali selezioni portino a una soluzione globale ottimale per il problema da risolvere. Gli algoritmi greedy spesso non sono troppo difficili da impostare, sono veloci (la complessità temporale è spesso una funzione lineare o molto una funzione di secondo ordine). Inoltre, questi programmi non sono difficili da debuggare e utilizzano meno memoria. Ma i risultati non sono sempre una soluzione ottimale.
Le strategie greedy vengono spesso utilizzate per risolvere il problema di ottimizzazione combinatoria costruendo un'opzione A. L'opzione A viene costruita selezionando ciascun componente Ai di A fino al completamento (abbastanza n componenti). Per ogni Ai, scegli Ai in modo ottimale. In questo modo è possibile che all'ultimo passaggio non si abbia altro da selezionare se non accettare l'ultimo valore rimasto.
Ci sono due componenti critici delle decisioni avide:
- Via della selezione golosa. È possibile selezionare la soluzione migliore al momento e risolvere il sottoproblema derivante dall'ultima selezione. La selezione degli algoritmi greedy può dipendere dalle selezioni precedenti. Ma non può dipendere da alcuna selezione futura o dalla soluzione dei sottoproblemi. L'algoritmo si evolve in modo da effettuare selezioni in un ciclo, riducendo allo stesso tempo il problema dato in sottoproblemi più piccoli.
- Sottostruttura ottimale. Si esegue la sottostruttura ottimale per un problema se la soluzione ottima di questo problema contiene soluzioni ottimali ai suoi sottoproblemi.
Un algoritmo greedy ha cinque componenti:
- Un insieme di candidati, da cui creare soluzioni.
- Una funzione di selezione, per selezionare il miglior candidato da aggiungere alla soluzione.
- Una funzione fattibile viene utilizzata per decidere se un candidato può essere utilizzato per costruire una soluzione.
- Una funzione obiettivo, che fissa il valore di una soluzione o di una soluzione incompleta.
- Una funzione di valutazione, che indica quando trovi una soluzione completa.
L'idea dell'avido
Con la prima idea, hai i seguenti passaggi di Greedy One:
- Ordina in ordine di valori non crescente.
- Considerare a turno i colli ordinati, mettere nello zaino il pacco in esame se la capacità residua dello zaino è sufficiente a contenerlo (il che significa che il peso totale dei colli messi nello zaino e il peso dei colli in esame non superano la capacità dello zaino).
Tuttavia, questo algoritmo avido non fornisce sempre la soluzione ottimale. Ecco un controesempio:
- I parametri del problema sono: n = 3; M = 19.
- I pacchetti: {i = 1; W[i] = 14; V[i] = 20}; {io = 2; W[i] = 6; V[i] = 16}; {i = 3; W[i] = 10; V[i] = 8} -> Ottimo rapporto qualità/prezzo ma anche ottimo peso.
- L'algoritmo selezionerà il pacchetto 1 con un valore totale di 20, mentre la soluzione ottima del problema verrà selezionata (pacchetto 2, pacchetto 3) con un valore totale di 24.
L'idea di Greedy Two
Con la seconda idea, hai i seguenti passaggi di Greedy Two:
- Ordina in ordine di peso non decrescente.
- Considerare a turno i colli ordinati, mettere nello zaino il pacco in esame se la capacità residua dello zaino è sufficiente a contenerlo (il che significa che il peso totale dei colli messi nello zaino e il peso dei colli in esame non superano la capacità dello zaino).
Tuttavia, questo algoritmo avido non fornisce sempre la soluzione ottimale. Ecco un controesempio:
- I parametri del problema sono: n = 3; M = 11.
- I pacchetti: {i = 1; W[i] = 5; V[i] = 10}; {io = 2; W[i] = 6; V[i] = 16}; {i = 3; W[i] = 10; V[i] = 28} -> Leggero ma anche il valore è molto leggero.
- L'algoritmo selezionerà (pacchetto 1, pacchetto 2) con un valore totale di 26, mentre la soluzione ottimale del problema è (pacchetto 3) con un valore totale di 28.
L'idea del Tre Avido
Con la terza idea, hai i seguenti passaggi di Greedy Three. Infatti, questo è l'algoritmo più ampiamente utilizzato.
- Ordinare i pacchetti in ordine non crescente del valore del costo unitario
. Hai:
- Considerare a turno i colli ordinati, mettere nello zaino il pacco in esame se la capacità residua dello zaino è sufficiente a contenerlo (il che significa che il peso totale dei colli messi nello zaino e il peso dei colli in esame non superano la capacità dello zaino).
L'idea: L'idea avida di questo problema è calcolare il 
rapporto di ciascuno 
. Quindi ordina questi rapporti in ordine decrescente. Sceglierai il più alto pacco e la capacità dello zaino può contenere quel pacco (rimanere > wi). Ogni volta che un pacco viene inserito nello zaino, si ridurrà anche la capacità dello zaino.
Modo per selezionare i pacchetti:
- Consideriamo la matrice dei costi unitari. Seleziona i pacchetti in base ai costi unitari decrescenti.
- Supponiamo di aver trovato una soluzione parziale: (x1, …, Xi).
- Il valore dello zaino si ottiene:
- Corrispondente al peso dei pacchi messi nello zaino:
- Pertanto, il limite di peso rimanente dello zaino è:
Passi dell'algoritmo
Vedi, questo è un problema per trovare max. L'elenco dei pacchetti è ordinato in ordine decrescente di costi unitari per considerare la ramificazione.
- Fase 1: La radice del nodo rappresenta lo stato iniziale dello zaino, dove non è stato selezionato alcun pacchetto.
- Valore totale = 0.
- Il limite superiore del nodo radice UpperBound = M * Costo unitario massimo.
- Fase 2: La radice del nodo avrà nodi figlio corrispondenti alla possibilità di selezionare il pacchetto con il costo unitario maggiore. Per ciascun nodo si ricalcolano i parametri:
- TotalValue = TotalValue (vecchio) + numero di pacchetti selezionati * valore di ciascun pacchetto.
- M = M (vecchio) – numero di colli selezionati * peso di ciascun pacco.
- UpperBound = TotalValue + M (nuovo) * Il costo unitario dell'imballaggio da considerare successivamente.
- Fase 3: Nei nodi figlio, darai priorità alla ramificazione per il nodo che ha il limite superiore più grande. I figli di questo nodo corrispondono alla capacità di selezionare il pacchetto successivo avente un costo unitario elevato. Per ciascun nodo è necessario ricalcolare i parametri TotalValue, M, UpperBound secondo la formula menzionata al punto 2.
- Fase 4: Ripetere il passo 3 con la nota: per i nodi con limite superiore inferiore o uguale al costo massimo temporaneo di un'opzione trovata, non è più necessario ramificarsi per quel nodo.
- Fase 5: Se tutti i nodi sono ramificati o tagliati, l'opzione più costosa è quella da cercare.
Pseudo codice per l'algoritmo:
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
La complessità dell'algoritmo:
- Se si utilizza un semplice algoritmo di ordinamento (selezione, bolla...), la complessità dell'intero problema è O(n2).
- Se si utilizza l'ordinamento rapido o l'ordinamento per fusione, la complessità dell'intero problema è O(nlogn).
Java codice per Tre Avidi
- Innanzitutto, definisci la classe KnapsackPackage. Questa classe ha proprietà: peso, valore e costo corrispondente di ciascun pacco. Il costo della proprietà di questa classe viene utilizzato per l'ordinamento dell'attività nell'algoritmo principale. Il valore di ciascun costo è il
rapporto di ciascun pacchetto.
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;
}
}
- Quindi crei una funzione per eseguire l'algoritmo 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);
}
Spiegazione del codice:
- Inizializza peso e valore per ogni pacco zaino.
- Ordina i pacchi zaino per costo con ordine decrescente.
- Se selezioni il pacchetto i.
- Se selezioni il numero del pacco i è sufficiente.
- Interrompi durante l'esplorazione di tutti i pacchetti.
In questo tutorial, hai due esempi. Ecco il codice Java per eseguire il programma sopra con due esempi:
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);
}
Hai l'output:
- Primo esempio:
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
- Secondo esempio:
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
Analizziamo il primo esempio:
- I parametri del problema sono: n = 4; M = 37.
- I pacchetti: {i = 1; W[i] = 15; V[i] = 30; Costo = 2.0}; {io = 2; W[i] = 10; V[i] = 25; Costo = 2.5}; {i = 3; W[i] = 2; V[i] = 4; Costo = 1.0}; {i = 4; W[i] = 4; V[i] = 6; Costo = 1.5}.
- Ordina i pacchetti nell'ordine in cui non aumenta il valore dei costi unitari. Hai: {i = 2} -> {io = 1} -> {io = 4} -> {i = 3}.
Passaggi per applicare l'algoritmo per il primo esempio:
- Definire x1, x2, x3, x4 è il numero di ciascun pacchetto selezionato, corrispondente al pacchetto {i = 2} -> {io = 1} -> {io = 4} -> {i = 3}.
- La radice del nodo N rappresenta lo stato in cui non hai selezionato alcun pacchetto. Poi:
- Valore totale = 0.
- M = 37 (come proposto).
- Limite superiore = 37 * 2.5 = 92.5, di cui 37 è M e 2.5 è il costo unitario del pacchetto {i = 2}.
- Con il pacchetto {i = 2} hai 4 possibilità: seleziona 3 pacchetti {i = 2} (x1 = 3); seleziona 2 pacchetti {i = 2} (x1 = 2); selezionare 1 pacchetto {i = 2} (x1 = 1) e non selezionare il pacchetto {i = 2} (x1 = 0). In accordo con queste 4 possibilità, si ramifica il nodo radice N in 4 figli N[1], N[2], N[3] e N[4].
- Per il nodo figlio N1, hai:
- TotalValue = 0 + 3 * 25 = 75, dove 3 è il numero del pacchetto {i = 2} selezionato e 25 è il valore di ciascun pacchetto {i = 2}.
- M = 37 – 3 * 10 = 7, dove 37 è la quantità iniziale dello zaino, 3 è il numero dei colli {i = 2}, 10 è il peso di ciascun pacco {i = 2}.
- Limite Superiore = 75 + 7 * 2 = 89, dove 75 è TotalValue, 7 è il peso rimanente dello zaino e 2 è il costo unitario del pacco {i = 1}.
- Allo stesso modo, è possibile calcolare i parametri per i nodi N[2], N[3] e N[4], in cui l'UpperBound è rispettivamente 84, 79 e 74.
- Tra i nodi N[1], N[2], N[3] e N[4], il nodo N[1] ha il limite superiore più grande, quindi diramerai prima il nodo N[1] nella speranza che ci sia un buon piano da questa direzione.
- Dal nodo N[1], hai un solo nodo figlio N[1-1] corrispondente a x2 = 0 (poiché il peso rimanente dello zaino è 7, mentre il peso di ciascun pacco {i = 1} è 15) . Dopo aver determinato i parametri per il pulsante N[1-1], il limite superiore di N[1-1] è 85.5.
- Si continua a ramificare il nodo N[1-1]. Il nodo N[1-1] ha 2 figli N[1-1-1] e N[1-1-2] corrispondenti a x3 = 1 e x3 = 0. Dopo aver determinato i parametri per questi due nodi, vedi che il Il limite superiore di N[1-1-1] è 84 e quello di N[1-1-2] è 82, quindi continui a ramificare il nodo N[1-1-1].
- Il nodo N[1-1-1] ha due figli, N[1-1-1-1] e N[1-1-1-2], corrispondenti a x4 = 1 e x4 = 0. Questi sono due nodi foglia (che rappresenta l'opzione) perché per ogni nodo è stato selezionato il numero di colli. In cui il nodo N[1-1-1-1] rappresenta l'opzione x1 = 3, x2 = 0, x3 = 1 e x4 = 1 per 83, mentre il nodo N[1-1-1-2] rappresenta l'opzione x1 = 3, x2 = 0, x3 = 1 e x4 = 01 su 81. Quindi il valore massimo temporaneo qui è 83.
- Tornando al nodo N[1-1-2], vedi che il limite superiore di N[1-1-2] è 82 < 83, quindi tagli il nodo N[1-1-2].
- Tornando al nodo N2, vedi che il limite superiore di N2 è 84 > 83, quindi continui a ramificare il nodo N2. Il nodo N2 ha due figli N[2-1] e N[2-2] corrispondenti a x2 = 1 e x2 = 0. Dopo aver calcolato i parametri per N[2-1] e N[2-2], vedi il limite superiore di N[2-1] è 83 e quello di N[2-2] è 75.25. Nessuno di questi valori è maggiore di 83, quindi entrambi i nodi vengono tagliati.
- Infine vengono tagliati anche i nodi N3 e N4.
- Quindi tutti i nodi dell'albero sono ramificati o tagliati, quindi la migliore soluzione temporanea è quella da cercare. Di conseguenza, è necessario selezionare 3 pacchi {i = 2}, 1 pacco {i = 4} e un pacco {i = 3} con un valore totale di 83, il peso totale è 36.
Con la stessa analisi del secondo esempio si ottiene il risultato: selezionare il pacchetto 4 (3 volte) e il pacchetto 5 (3 volte).
Python3 codice per Tre Avido
- Innanzitutto, definisci la classe 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
- Quindi crei una funzione per eseguire l'algoritmo 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)
Spiegazione del codice:
- Inizializza peso e valore per ogni pacco zaino.
- Ordina i pacchi zaino per costo con ordine decrescente.
- Se selezioni il pacchetto i.
- Se selezioni il numero del pacco i è sufficiente.
- Interrompi durante l'esplorazione di tutti i pacchetti.
Qui è Python3 codice per eseguire il programma sopra con il primo esempio:
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)
Hai l'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
Codice C# per Greedy Three
- Innanzitutto, definisci la classe 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; }
}
}
}
- Quindi crei una funzione per eseguire l'algoritmo 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);
}
}
}
Spiegazione del codice:
- Inizializza peso e valore per ogni pacco zaino.
- Ordina i pacchi zaino per costo con ordine decrescente.
- Se selezioni il pacchetto i.
- Se selezioni il numero del pacco i è sufficiente.
- Interrompi durante l'esplorazione di tutti i pacchetti.
Ecco il codice C# per eseguire il programma sopra con il primo esempio:
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);
}
Hai l'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
Controesempio di Greedy Three
L'algoritmo di Greedy Three risolve rapidamente e in alcuni casi può anche essere ottimale. Tuttavia, in alcuni casi particolari, non fornisce la soluzione ottimale. Ecco un controesempio:
- I parametri del problema sono: n = 3; M = 10.
- I pacchetti: {i = 1; W[i] = 7; V[i] = 9; Costo = 9/7}; {io = 2; W[i] = 6; V[i] = 6; Costo = 1}; {i = 3; W[i] = 4; V[i] = 4; Costo = 1}.
- L'algoritmo selezionerà (pacchetto 1) con un valore totale pari a 9, mentre la soluzione ottimale del problema sarà (pacchetto 2, pacchetto 3) con un valore totale pari a 10.
Ecco il codice Java per eseguire il programma sopra con il controesempio:
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);
}
Ecco il risultato:
Pack 0 - Weight 7.0 - Value 9.0 Max Value: 9.0
Questo è tutto per il problema dello Zaino Frazionario.
