Problem frakcijskog naprtnjače: pohlepni algoritam s primjerom

Što je pohlepna strategija?

Pohlepni algoritmi odabrati najbolji lokalni izbor u svakom koraku u nadi da će lanac lokalnih optimuma proizvesti globalno optimalno rješenje. Poput dinamičkog programiranja, oni ciljaju na probleme optimizacije, ali se nikada ne osvrću unatrag kako bi preispitali ranije odluke.

Pohlepni algoritmi su obično jednostavni za pisanje, brzi (često linearno ili kvadratno vrijeme), laki za otklanjanje pogrešaka i malo koriste memoriju. Nedostatak je što rezultat nije uvijek optimalan, pa strategija funkcionira samo za probleme koji imaju dokazano pohlepno sigurnu strukturu.

Pohlepne strategije rješavaju kombinatornu optimizaciju izgradnjom rješenja A, jednu komponentu Ai odjednom. U svakom koraku optimalno birate Ai pod trenutnim ograničenjima i smanjujete problem na manji podproblem.

Da bi pohlepna metoda bila ispravna, moraju biti zadovoljena dva svojstva:

1. Svojstvo pohlepnog izbora: Lokalni optimum u svakom koraku vodi do globalnog optimuma. Izbor ovisi o prošlim odlukama, ali ne i o budućim.
2. Optimalna podstruktura: Optimalno rješenje cijelog problema sadrži optimalna rješenja njegovih podproblema.

Pohlepni algoritam ima pet komponenti:

1. Skup kandidata iz kojeg se grade rješenja.
2. Funkcija odabira koja odabire najboljeg sljedećeg kandidata.
3. Funkcija izvedivosti koja provjerava može li kandidat proširiti trenutno parcijalno rješenje.
4. Ciljna funkcija koja vrednuje potpuno ili djelomično rješenje.
5. Funkcija evaluacije koja signalizira kada je rješenje dovršeno.

Ideja Greedy One

Pohlepni sortira pakete samo po vrijednosti:

• Sortiraj pakete po nerastućem redoslijedu vrijednosti.
• Prošetajte sortiranim popisom i dodajte svaki paket u ruksak ako ga preostali kapacitet može primiti.

Ovo pravilo ne daje uvijek optimalni odgovor. Protuprimjer:

• Parametri: n = 3, M = 19.
• Paketi: {i = 1; W = 14; V = 20}, {i = 2; W = 6; V = 16}, {i = 3; W = 10; V = 8} — visoka vrijednost, ali i velika težina.
• Pohlepni bira paket 1 s ukupnom vrijednošću 20, dok optimalni izbor (paket 2, paket 3) doseže 24.

Ideja Greedy Two

Pohlepni Dvije vrste paketa samo po težini:

• Sortirajte pakete po težini, ne opadajuće.
• Prošetajte sortiranim popisom i dodajte svaki paket u ruksak ako ga preostali kapacitet može primiti.

Ovo pravilo također nije optimalno. Protuprimjer:

• Parametri: n = 3, M = 11.
• Paketi: {i = 1; W = 5; V = 10}, {i = 2; W = 6; V = 16}, {i = 3; W = 10; V = 28} — mala težina, ali niska vrijednost.
• Pohlepni Dva izbora (paket 1, paket 2) s ukupnom vrijednošću 26, dok optimalni izbor (paket 3) doseže 28.

Ideja Greedy Three

Greedy Three ispravlja oba neuspjeha kombiniranjem vrijednosti i težine u jedan ključ rangiranja. To je standardna metoda za problem frakcijskog ruksaka.

• Izračunajte jediničnu cijenu V[i] / W[i] za svaki paket.
• Sortirajte pakete po nerastućem redoslijedu cijene po jedinici.
• Prođite sortiranim popisom i dodajte svaki paket ako ga preostali kapacitet može primiti.

Pohlepna tri sortiranja po jediničnoj cijeni V[i] / W[i]

Ideja: Izračunajte omjer vrijednosti i težine V[i] / W[i] za svaki paket, sortirajte u silaznom redoslijedu i prvo uzmite najveći dostupni omjer dok se ruksak ne napuni.

Za istinito razlomački varijanta, kada sljedeći paket ne može stati cijeli, uzmite razlomak koji točno ispunjava preostali kapacitet. To dodatno pravilo čini Greedy Three dokazivo optimalnim na Fractional Knapsack.

Koraci algoritma

Za varijantu grananja i veza 0/1, sortirana lista jediničnih troškova pokreće stablo pretraživanja:

• Korak 1: Korijenski čvor predstavlja prazan ruksak. UkupnaVrijednost = 0. GornjaGranica = M × maksimalna cijena po jedinici.
• Korak 2: Granajte korijen prema broju kopija paketa s najvećim omjerom koji stane. Za svako dijete ponovno izračunajte TotalValue, preostali kapacitet M i UpperBound.
• Korak 3: Prvo proširite dijete s najvećom gornjom granicom, u nadi da ćete brzo pronaći snažno rješenje.
• Korak 4: Orezi svaki čvor čija gornja granica nije bolja od trenutno najboljeg potpunog rješenja.
• Korak 5: Kada se svaki čvor proširi ili oreže, trenutno najbolje potpuno rješenje je optimalno.

Pseudokod za čisti pohlepni algoritam frakcijskog ruksaka:

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

Složenost algoritma:

• Korištenje jednostavnog sortiranja (odabir ili mjehurić): O(n²).
• Korištenje brzog sortiranja ili sortiranja spajanjem: O(n log n), dominira korak sortiranja.

Java Code za Pohlepnu trojku

Definirajte KnapsackPackage klasa s težinom, vrijednošću i izvedenim troškom (omjer V/W koji se koristi za sortiranje):

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

Zatim kreirajte funkciju koja implementira 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);
}

Funkcija naprtnjačaGreProc() in Java

Objašnjenje koda:

1. Zamotajte svaki ulaz u KnapsackPackage pa se ključ sortiranja (omjer V/W) unaprijed izračunava.
2. Sortiraj po silaznom redoslijedu cijene.
3. Uzmite svako pakiranje cijelo ako vam odgovara.
4. Uzmite dio sljedećeg pakiranja kako biste popunili preostali kapacitet.
5. Zaustavite čim preostali kapacitet dosegne nulu.

Ispravak napomene: izvornik Java petlja napredno i samo kada paket nije odgovarao, što je uzrokovalo ponovljeno uzimanje istog paketa. Gornja verzija pomiče jedan paket po iteraciji i dodaje korak djelomičnog punjenja, što odgovara pravom pravilu djelomičnog ruksaka.

Java upravljački program koji pokreće algoritam na obrađenom primjeru:

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 za Pohlepnu trojku

Prvo definirajte KnapsackPackage razreda. The __lt__ metoda omogućuje izravno sortiranje po cijeni:

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

Zatim implementirajte rutinu s djelomičnim ruksakom:

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)

Funkcija naprtnjačaGreProc() in Python

Ispravak napomene: izvornik Python klasa je definirala prazno __init__ bez tijela, što podiže IndentationErrorGornja verzija uklanja prazan konstruktor jer nije potreban.

Upravljački program koji pokreće algoritam na prvom primjeru:

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 za Pohlepnu trojku

Definirajte KnapsackPackage razred:

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

Implementirajte Greedy Three s korakom frakcijskog popunjavanja:

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

Funkcija KnapsackGreProc() u C#

Protuprimjer: Pohlepna trojka na ruksaku 0/1

Pohlepna trojka je optimalna za Fractional varijantu, ali na 0/1 Knapsack-u (gdje se predmeti ne mogu dijeliti) može se pobijediti. Protuprimjer:

• Parametri: n = 3, M = 10.
• Paketi: {i = 1; W = 7; V = 9; trošak = 9/7}, {i = 2; W = 6; V = 6; trošak = 1}, {i = 3; W = 4; V = 4; trošak = 1}.
• Pohlepna trojka bira paket 1 za ukupnu vrijednost 9, dok optimalni izbor 0/1 (paket 2, paket 3) doseže 10.

Pouka: koristite Greedy Three samo kada su dopušteni razlomci. Za varijantu 0/1 koristite Dinamičko programiranje umjesto.

Primjena djelomičnog ruksaka

• Utovar tereta gdje se tekuća, praškasta ili rasuta roba može podijeliti po težini.
• Raspodjela portfelja po investicijskim opcijama koje prihvaćaju djelomično financiranje.
• Dijeljenje propusnosti u oblaku gdje tokovi mogu potrošiti samo dio veze.
• Raspoređivanje CPU-a prema modelu dijeljenog vremenskog odsječka s djeljivim radnim opterećenjima.
• Raspodjela AI resursa gdje zadatak obuke može koristiti dio GPU-a.

Pitanja i odgovori