Problema dello zaino frazionario: algoritmo Greedy con esempio

Cos'è la strategia golosa?

Algoritmi avidi Ad ogni passo, scelgono l'opzione locale migliore nella speranza che una catena di ottimi locali produca una soluzione globalmente ottimale. Come la programmazione dinamica, si concentrano su problemi di ottimizzazione, ma non tornano mai indietro per riconsiderare le decisioni prese in precedenza.

Gli algoritmi greedy sono generalmente semplici da scrivere, veloci (spesso con complessità temporale lineare o quadratica), facili da debuggare e leggeri in termini di memoria. Il compromesso è che il risultato non è sempre ottimale, quindi la strategia funziona solo per problemi che presentano una struttura dimostrata essere sicura per gli algoritmi greedy.

Le strategie greedy risolvono l'ottimizzazione combinatoria costruendo una soluzione A un componente Ai alla volta. Ad ogni passaggio si sceglie Ai in modo ottimale in base ai vincoli correnti e si riduce il problema a un sottoproblema più piccolo.

Perché un metodo greedy sia corretto, devono valere due proprietà:

1. Proprietà di scelta avida: Un ottimo locale ad ogni passo conduce a un ottimo globale. La scelta dipende dalle decisioni passate, non da quelle future.
2. Sottostruttura ottimale: La soluzione ottimale dell'intero problema contiene le soluzioni ottimali dei suoi sottoproblemi.

Un algoritmo greedy ha cinque componenti:

1. Un insieme di candidati a partire dai quali vengono costruite le soluzioni.
2. Una funzione di selezione che sceglie il miglior candidato successivo.
3. Una funzione di fattibilità che verifica se un candidato può estendere l'attuale soluzione parziale.
4. Una funzione obiettivo che valuta una soluzione completa o parziale.
5. Una funzione di valutazione che segnala quando la soluzione è completa.

L'idea dell'avido

Greedy One ordina i pacchetti esclusivamente in base al valore:

• Ordina i pacchi in ordine di valore non crescente.
• Percorri l'elenco ordinato e aggiungi ogni pacco allo zaino se la capacità rimanente lo consente.

Questa regola non fornisce sempre la risposta ottimale. Controesempio:

• Parametri: n = 3, M = 19.
• Pacchetti: {i = 1; W = 14; V = 20}, {i = 2; W = 6; V = 16}, {i = 3; W = 10; V = 8} — valore elevato ma anche peso elevato.
• Greedy One sceglie il pacchetto 1 con un valore totale di 20, mentre la scelta ottimale (pacchetto 2, pacchetto 3) raggiunge 24.

L'idea di Greedy Two

Greedy Two ordina i pacchi solo in base al peso:

• Ordina i pacchi in ordine di peso non decrescente.
• Percorri l'elenco ordinato e aggiungi ogni pacco allo zaino se la capacità rimanente lo consente.

Anche questa regola non è ottimale. Controesempio:

• Parametri: n = 3, M = 11.
• Confezioni: {i = 1; W = 5; V = 10}, {i = 2; W = 6; V = 16}, {i = 3; W = 10; V = 28} — peso ridotto ma valore basso.
• Greedy sceglie due opzioni (pacchetto 1, pacchetto 2) per un valore totale di 26, mentre la scelta ottimale (pacchetto 3) raggiunge 28.

L'idea del Tre Avido

Greedy Three risolve entrambi i problemi combinando valore e peso in un'unica chiave di classificazione. È il metodo standard per il problema dello zaino frazionario.

• Calcola il costo unitario V[i] / W[i] per ogni confezione.
• Ordina i pacchi in ordine decrescente di costo unitario.
• Esamina l'elenco ordinato e aggiungi ogni pacco se lo spazio rimanente lo consente.

Avido Tre ordinamenti in base al costo unitario V[i] / W[i]

Idea: Calcola il rapporto valore-peso V[i] / W[i] per ogni pacco, ordinalo in ordine decrescente e prendi prima il rapporto più grande disponibile finché lo zaino non è pieno.

Per il vero Frazionale variante, quando il pacchetto successivo non può entrare intero, prendi una frazione che riempia esattamente la capacità rimanente. Questa regola aggiuntiva è ciò che rende Greedy Three dimostrabilmente ottimale su Fractional Knapsack.

Passaggi dell'algoritmo

Per la variante branch-and-bound 0/1, l'elenco ordinato dei costi unitari genera un albero di ricerca:

• Passo 1: Il nodo radice rappresenta uno zaino vuoto. Valore totale = 0. Limite superiore = M × costo unitario massimo.
• Passo 2: Dirama la radice in base al numero di copie del pacchetto con il rapporto più elevato che possono essere contenute. Per ogni figlio, ricalcola TotalValue, la capacità rimanente M e UpperBound.
• Passo 3: Espandere prima il figlio con il limite superiore più grande, nella speranza di trovare rapidamente una soluzione robusta.
• Passo 4: Elimina tutti i nodi il cui limite superiore non è migliore della migliore soluzione completa corrente.
• Passo 5: Quando ogni nodo viene espanso o potato, la migliore soluzione completa corrente è ottimale.

Pseudocodice per l'algoritmo greedy Fractional Knapsack puro:

Fractional Knapsack (Array W, Array V, int M)
1. for i <- 1 to size(V)
2.     cost[i] <- V[i] / W[i]
3. Sort-Descending(cost)
4. total <- 0
5. i <- 1
6. while (i <= size(V) and M > 0)
7.     if W[i] <= M
8.         M <- M - W[i]
9.         total <- total + V[i]
10.        i <- i + 1
11.    else
12.        total <- total + V[i] * (M / W[i])
13.        M <- 0

Complessità dell'algoritmo:

• Utilizzando un semplice ordinamento (selezione o bolla): O(n²).
• Utilizzando quick sort o merge sort: O(n log n), dominato dalla fase di ordinamento.

Java Code per Greedy Three

Definire il KnapsackPackage classe con peso, valore e costo derivato (il rapporto V/W utilizzato per la classificazione):

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 = Double.valueOf(value / weight);
    }

    public double getWeight() { return weight; }

    public double getValue() { return value; }

    public Double getCost()  { return cost; }
}

Quindi crea la funzione che implementa 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 a, KnapsackPackage b) {
            return b.getCost().compareTo(a.getCost());
        }
    });

    double remain = M;
    double result = 0d;

    for (int i = 0; i < n && remain > 0; i++) {
        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());
        } else {
            double fraction = remain / packs[i].getWeight();
            result += packs[i].getValue() * fraction;
            System.out.println("Pack " + i + " - Fraction " + fraction
                             + " - Value " + packs[i].getValue() * fraction);
            remain = 0;
        }
    }

    System.out.println("Max Value:\t" + result);
}

Funzione zainoGreProc() in Java

Spiegazione del codice:

1. Avvolgi ogni input in un KnapsackPackage quindi il criterio di ordinamento (rapporto V/W) è precalcolato.
2. Ordina in ordine decrescente di costo.
3. Prendi ogni confezione intera se ci sta.
4. Prendi una parte della confezione successiva per riempire lo spazio rimanente.
5. Interrompere l'operazione non appena la capacità residua raggiunge lo zero.

Nota di correzione: l'originale Java ciclo avanzato i solo quando un pacco non entrava, il che causava il prelievo ripetuto dello stesso pacco. La versione sopra riportata avanza di un pacco per iterazione e aggiunge una fase di riempimento frazionario, corrispondente alla vera regola dello zaino frazionario.

Java driver che esegue l'algoritmo su un esempio pratico:

public void run() {
    int W[] = new int[]{15, 10, 2, 4};
    int V[] = new int[]{30, 25, 2, 6};
    int M = 37;
    int n = V.length;
    knapsackGreProc(W, V, M, n);
}

Python3 Code per Greedy Three

Innanzitutto definiamo il KnapsackPackage classe. Il __lt__ Questo metodo permette di ordinarlo direttamente in base al costo:

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 implementa la routine dello zaino frazionario:

class FractionalKnapsack(object):

    def knapsackGreProc(self, W, V, M, n):
        packs = [KnapsackPackage(W[i], V[i]) for i in range(n)]
        packs.sort(reverse=True)

        remain = M
        result = 0

        for i in range(n):
            if remain == 0:
                break
            if packs[i].weight <= remain:
                remain -= packs[i].weight
                result += packs[i].value
                print("Pack", i, "- Weight", packs[i].weight, "- Value", packs[i].value)
            else:
                fraction = remain / packs[i].weight
                result += packs[i].value * fraction
                print("Pack", i, "- Fraction", fraction,
                      "- Value", packs[i].value * fraction)
                remain = 0

        print("Max Value:", result)

Funzione zainoGreProc() in Python

Nota di correzione: l'originale Python classe definita vuota __init__ senza corpo, il che solleva IndentationErrorLa versione sopra riportata rimuove il costruttore vuoto perché non è necessario.

Driver che esegue l'algoritmo sul 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)

C# Code per Greedy Three

Definire il KnapsackPackage classe:

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   = value / weight;
        }

        public double Weight { get { return weight; } }
        public double Value  { get { return value; } }
        public double Cost   { get { return cost; } }
    }
}

Implementare Greedy Three con una fase di riempimento frazionario:

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,
        (a, b) => b.Cost.CompareTo(a.Cost));

    double remain = M;
    double result = 0d;

    for (int i = 0; i < n && remain > 0; i++)
    {
        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);
        }
        else
        {
            double fraction = remain / packs[i].Weight;
            result += packs[i].Value * fraction;
            Console.WriteLine("Pack " + i + " - Fraction " + fraction
                            + " - Value " + packs[i].Value * fraction);
            remain = 0;
        }
    }

    Console.WriteLine("Max Value:\t" + result);
}

Funzione ZainoGreProc() in C#

Controesempio: Tre avidi su 0/1 zaino

Greedy Three è ottimale per la variante Frazionaria, ma nello zaino 0/1 (dove gli oggetti non possono essere divisi) può essere battuto. Controesempio:

• Parametri: n = 3, M = 10.
• Pacchetti: {i = 1; W = 7; V = 9; costo = 9/7}, {i = 2; W = 6; V = 6; costo = 1}, {i = 3; W = 4; V = 4; costo = 1}.
• Greedy Three sceglie il pacchetto 1 per un valore totale di 9, mentre la scelta ottimale 0/1 (pacchetto 2, pacchetto 3) raggiunge 10.

La lezione: usa Greedy Three solo quando sono ammesse le frazioni. Per la variante 0/1, usa Programmazione dinamica anziché.

Applicazioni dello zaino frazionato

• Operazioni di carico in cui merci liquide, in polvere o sfuse possono essere suddivise in base al peso.
• Allocazione del portafoglio tra opzioni di investimento che accettano finanziamenti parziali.
• Condivisione della larghezza di banda nel cloud, dove i flussi possono consumare solo una frazione di un collegamento.
• Pianificazione della CPU secondo un modello a slice di tempo condiviso con carichi di lavoro divisibili.
• Allocazione delle risorse per l'IA, dove un processo di addestramento può utilizzare solo una frazione di una GPU.

DOMANDE FREQUENTI