Problemă de rucsac fracționat: algoritm lacom cu exemplu

Ce este Greedy Strategy?

Algoritmi lacomi aleg cea mai bună variantă locală la fiecare pas, în speranța că un lanț de optime locale produce o soluție optimă la nivel global. La fel ca Programarea Dinamică, acestea vizează problemele de optimizare, dar nu privesc niciodată înapoi pentru a reconsidera deciziile anterioare.

Algoritmii greedy sunt de obicei simplu de scris, rapizi (adesea cu timp liniar sau pătratic), ușor de depanat și consumă puțină memorie. Compromisul este că rezultatul nu este întotdeauna optim, așadar strategia funcționează doar pentru problemele care au o structură greedy-safe dovedită.

Strategiile greedy rezolvă optimizarea combinatorie prin construirea unei soluții A, câte o componentă Ai la un moment dat. La fiecare pas, alegeți Ai optim în limitele constrângerilor actuale și reduceți problema la o subproblemă mai mică.

Două proprietăți trebuie să fie îndeplinite pentru ca o metodă greedy să fie corectă:

1. Proprietatea alegerii lacome: Un optim local la fiecare pas duce la un optim global. Alegerea depinde de deciziile trecute, dar nu și de cele viitoare.
2. Substructură optimă: Soluția optimă a întregii probleme conține soluții optime ale subproblemelor sale.

Un algoritm lacom are cinci componente:

1. Un set de candidați din care se construiesc soluții.
2. O funcție de selecție care alege cel mai bun candidat următor.
3. O funcție de fezabilitate care verifică dacă un candidat poate extinde soluția parțială curentă.
4. O funcție obiectiv care valorizează o soluție completă sau parțială.
5. O funcție de evaluare care semnalează când soluția este completă.

Ideea Lacomului

Greedy One sortează pachetele doar după valoare:

• Sortați pachetele în ordine necrescătoare a valorii.
• Parcurge lista sortată și adaugă fiecare pachet în rucsac, dacă spațiul rămas îl poate conține.

Această regulă nu oferă întotdeauna răspunsul optim. Contraexemplu:

• Parametri: n = 3, M = 19.
• Pachete: {i = 1; W = 14; V = 20}, {i = 2; W = 6; V = 16}, {i = 3; W = 10; V = 8} — valoare mare, dar și greutate mare.
• Cel lacom alege pachetul 1 cu o valoare totală de 20, în timp ce alegerea optimă (pachetul 2, pachetul 3) ajunge la 24.

Ideea lui Greedy Two

Greedy Two sortează pachetele doar în funcție de greutate:

• Sortați coletele în ordine nedescrescătoare a greutății.
• Parcurge lista sortată și adaugă fiecare pachet în rucsac, dacă spațiul rămas îl poate conține.

Nici această regulă nu reușește să fie optimă. Contraexemplu:

• Parametri: n = 3, M = 11.
• Pachete: {i = 1; W = 5; V = 10}, {i = 2; W = 6; V = 16}, {i = 3; W = 10; V = 28} — greutate redusă, dar valoare scăzută.
• Două alegeri lacome (pachetul 1, pachetul 2) cu o valoare totală de 26, în timp ce alegerea optimă (pachetul 3) ajunge la 28.

Ideea lui Greedy Three

Greedy Three corectează ambele erori prin combinarea valorii și a ponderării într-o singură cheie de clasament. Este metoda standard pentru Problema Rucsacului Fracțional.

• Calculați costul unitar V[i] / W[i] pentru fiecare pachet.
• Sortați pachetele în ordine necrescătoare a costului unitar.
• Parcurgeți lista sortată și adăugați fiecare pachet dacă capacitatea rămasă îl poate conține.

Greedy Three sortează după costul unitar V[i] / W[i]

Ideea: Calculați raportul valoare-greutate V[i] / W[i] pentru fiecare pachet, sortați în ordine descrescătoare și luați primul cel mai mare raport disponibil până când rucsacul este plin.

Pentru adevărat Fracționar variantă, când următorul pachet nu poate încăpea întreg, se ia o fracție care umple exact capacitatea rămasă. Această regulă suplimentară este ceea ce face ca Greedy Three să fie demonstrabil optim pe Fractional Knapsack.

Pașii algoritmului

Pentru varianta 0/1 branch-and-bound, lista de costuri unitare sortate conduce la un arbore de căutare:

• Pasul 1: Nodul rădăcină reprezintă un rucsac gol. TotalValue = 0. UpperBound = M × cost unitar maxim.
• Pasul 2: Ramificați rădăcina în funcție de numărul de copii ale pachetului cu cel mai mare raport care încape. Pentru fiecare copil, recalculați TotalValue, capacitatea rămasă M și UpperBound.
• Pasul 3: Extindeți mai întâi copilul cu cea mai mare UpperBound, în speranța de a găsi rapid o soluție puternică.
• Pasul 4: Eliminați orice nod a cărui limită superioară nu este mai bună decât cea mai bună soluție completă curentă.
• Pasul 5: Când fiecare nod este fie extins, fie eliminat, soluția completă curentă este optimă.

Pseudocod pentru algoritmul greedy pur de tip Fractional Knapsack:

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

Complexitatea algoritmului:

• Folosind o sortare simplă (selecție sau bulă): O(n²).
• Utilizarea sortării rapide sau a sortării prin îmbinare: O(n log n), dominat de pasul de sortare.

Java Code pentru Greedy Three

Definiți KnapsackPackage clasă cu greutate, valoare și cost derivat (raportul V/W utilizat pentru sortare):

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; }
}

Apoi creați funcția care implementează 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);
}

Funcția knapsackGreProc() în Java

Explicația codului:

1. Încadrați fiecare intrare într-o KnapsackPackage deci cheia de sortare (raportul V/W) este precalculată.
2. Sortați în ordine descrescătoare a costului.
3. Luați fiecare pachet întreg, dacă încape.
4. Luați o fracțiune din următorul pachet pentru a umple capacitatea rămasă.
5. Opriți-vă imediat ce capacitatea rămasă ajunge la zero.

Notă de corecție: originală Java buclă avansată i numai atunci când un pachet nu se potrivea, ceea ce a cauzat preluarea repetată a aceluiași pachet. Versiunea de mai sus avansează cu un pachet per iterație și adaugă un pas de umplere fracționară, corespunzând regulii reale a rucsacului fracționar.

Java driverul care rulează algoritmul pe un exemplu funcțional:

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 pentru Greedy Three

Mai întâi definiți KnapsackPackage clasă. __lt__ Metoda o face direct sortabilă după cost:

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 implementați rutina Fractional Knapsack:

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)

Funcția knapsackGreProc() în Python

Notă de corecție: originală Python clasa a definit un gol __init__ fără corp, ceea ce ridică IndentationErrorVersiunea de mai sus elimină constructorul gol deoarece nu este necesar niciunul.

Driverul care rulează algoritmul pe 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)

C# Code pentru Greedy Three

Definiți KnapsackPackage clasă:

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; } }
    }
}

Implementați Greedy Three cu un pas de umplere fracționară:

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);
}

Funcția KnapsackGreProc() în C#

Contra-exemplu: Greedy Three pe rucsac 0/1

Greedy Three este optim pentru varianta Fracțională, dar pe Rucsacul 0/1 (unde obiectele nu pot fi împărțite) poate fi învins. Contraexemplu:

• Parametri: n = 3, M = 10.
• Pachete: {i = 1; W = 7; V = 9; cost = 9/7}, {i = 2; W = 6; V = 6; cost = 1}, {i = 3; W = 4; V = 4; cost = 1}.
• Greedy Three alege pachetul 1 pentru o valoare totală de 9, în timp ce alegerea optimă 0/1 (pachetul 2, pachetul 3) ajunge la 10.

Lecția: folosiți Greedy Three doar atunci când sunt permise fracții. Pentru varianta 0/1, folosiți Programare dinamică in schimb.

Aplicații ale rucsacului fracțional

• Încărcare de marfă unde mărfurile lichide, sub formă de pulbere sau vrac pot fi împărțite în greutate.
• Alocarea portofoliului între opțiuni de investiții care acceptă finanțare parțială.
• Partajarea lățimii de bandă în cloud, unde fluxurile pot consuma o fracțiune dintr-o legătură.
• Planificarea CPU sub un model de felii de timp partajate cu sarcini de lucru divizibile.
• Alocare de resurse AI unde un job de antrenament poate utiliza o fracțiune dintr-un GPU.

Întrebări frecvente