Fractionele knapzak Probleem: hebzuchtig algoritme met voorbeeld

Wat is hebzuchtige strategie?

Hebzuchtige algoritmen Bij elke stap wordt de beste lokale optie gekozen in de hoop dat een reeks lokale optima een globaal optimale oplossing oplevert. Net als dynamische programmering richten ze zich op optimalisatieproblemen, maar ze kijken nooit terug om eerdere beslissingen te herzien.

Gierige algoritmen zijn doorgaans eenvoudig te schrijven, snel (vaak in lineaire of kwadratische tijd), makkelijk te debuggen en geheugenarm. Het nadeel is dat het resultaat niet altijd optimaal is, waardoor de strategie alleen werkt voor problemen met een bewezen gierige-veilige structuur.

Gierige strategieën lossen combinatorische optimalisatieproblemen op door een oplossing A component voor component Ai op te bouwen. Bij elke stap kies je Ai optimaal onder de gegeven beperkingen en verklein je het probleem tot een kleiner deelprobleem.

Twee eigenschappen moeten gelden wil een gulzige methode correct zijn:

1. Eigenschap van de hebzuchtige keuze: Een lokaal optimum bij elke stap leidt tot een globaal optimum. De keuze hangt af van eerdere beslissingen, maar niet van toekomstige.
2. Optimale substructuur: De optimale oplossing van het gehele probleem bevat de optimale oplossingen van de deelproblemen.

Een hebzuchtig algoritme bestaat uit vijf componenten:

1. Een verzameling kandidaten waaruit oplossingen worden opgebouwd.
2. Een selectiefunctie die de beste volgende kandidaat kiest.
3. Een haalbaarheidsfunctie die controleert of een kandidaat de huidige gedeeltelijke oplossing kan uitbreiden.
4. Een doelfunctie die een volledige of gedeeltelijke oplossing waardeert.
5. Een evaluatiefunctie die aangeeft wanneer de oplossing compleet is.

Het idee van hebzuchtige

Greedy One sorteert pakketten uitsluitend op waarde:

• Sorteer de pakketten in niet-oplopende volgorde van waarde.
• Loop de gesorteerde lijst door en voeg elk pakket toe aan de rugzak als de resterende capaciteit dit toelaat.

Deze regel levert niet altijd het optimale antwoord op. Tegenvoorbeeld:

• Parameters: n = 3, M = 19.
• Pakketten: {i = 1; W = 14; V = 20}, {i = 2; W = 6; V = 16}, {i = 3; W = 10; V = 8} — hoge waarde maar ook hoog gewicht.
• Gierig kiest pakket 1 met een totale waarde van 20, terwijl de optimale keuze (pakket 2, pakket 3) een waarde van 24 oplevert.

Het idee van Greedy Two

Greedy Two sorteert pakketten uitsluitend op gewicht:

• Sorteer de pakketten in volgorde van gewicht (niet aflopend).
• Loop de gesorteerde lijst door en voeg elk pakket toe aan de rugzak als de resterende capaciteit dit toelaat.

Ook deze regel is niet optimaal. Tegenvoorbeeld:

• Parameters: n = 3, M = 11.
• Pakketten: {i = 1; W = 5; V = 10}, {i = 2; W = 6; V = 16}, {i = 3; W = 10; V = 28} — lichtgewicht maar lage waarde.
• Gierig kiest twee opties (pakket 1, pakket 2) met een totale waarde van 26, terwijl de optimale keuze (pakket 3) een waarde van 28 oplevert.

Het idee van hebzuchtige drie

Greedy Three lost beide tekortkomingen op door waarde en gewicht te combineren tot één enkele rangschikkingssleutel. Het is de standaardmethode voor het fractionele knapzakprobleem.

• Bereken de eenheidskosten V[i] / W[i] voor elk pakket.
• Sorteer de pakketten in niet-oplopende volgorde van de eenheidskosten.
• Loop de gesorteerde lijst door en voeg elk pakket toe als de resterende capaciteit dit toelaat.

Greedy Three sorteert op eenheidskosten V[i] / W[i]

Idee: Bereken de waarde-gewichtverhouding V[i] / W[i] voor elk pakket, sorteer in aflopende volgorde en neem de grootste beschikbare verhouding als eerste totdat de rugzak vol is.

Voor de ware Fractioneel Als variant hiervan, en het volgende pakket niet volledig past, neem dan een fractie die precies de resterende capaciteit vult. Die extra regel maakt Greedy Three aantoonbaar optimaal voor Fractional Knapsack.

Stappen van het algoritme

Bij de 0/1 branch-and-bound variant stuurt de gesorteerde lijst met eenheidskosten een zoekboom aan:

• Stap 1: Het wortelknooppunt vertegenwoordigt een lege rugzak. Totale waarde = 0. Bovengrens = M × maximale eenheidskosten.
• Stap 2: Vertak de wortel op basis van het aantal exemplaren van het pakket met de grootste verhouding dat erin past. Bereken voor elk kind de TotalValue, de resterende capaciteit M en de UpperBound opnieuw.
• Stap 3: Begin met het kind met de grootste bovengrens, in de hoop snel een sterke oplossing te vinden.
• Stap 4: Verwijder alle knooppunten waarvan de UpperBound niet beter is dan de huidige beste complete oplossing.
• Stap 5: Wanneer elk knooppunt is uitgebreid of gesnoeid, is de huidige beste complete oplossing optimaal.

Pseudocode voor het pure fractionele knapsack-gulzige algoritme:

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

Complexiteit van het algoritme:

• Met behulp van een eenvoudige sorteermethode (selectie of bubble sort): O(n)²).
• Bij gebruik van quicksort of mergesort: O(n log n), waarbij de sorteerstap het meest complex is.

Java Code voor Gierige Drie

Definieer de KnapsackPackage klasse met gewicht, waarde en afgeleide kosten (de V/W-verhouding die wordt gebruikt voor sortering):

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

Maak vervolgens de functie die Greedy Three implementeert:

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

Functie knapzakGreProc() in Java

Toelichting code:

1. Wikkel elke invoer in een KnapsackPackage De sorteersleutel (V/W-verhouding) is dus vooraf berekend.
2. Sorteer in aflopende volgorde van prijs.
3. Neem elk pakket in zijn geheel mee, indien het past.
4. Neem een ​​deel van de volgende verpakking om de resterende ruimte aan te vullen.
5. Stop zodra de resterende capaciteit nul bereikt.

Correctie-opmerking: het origineel Java lus geavanceerd i Alleen wanneer een pakket niet paste, waardoor hetzelfde pakket herhaaldelijk werd gepakt. De bovenstaande versie schuift één pakket per iteratie op en voegt een stap voor gedeeltelijke vulling toe, overeenkomend met de echte Fractional Knapsack-regel.

Java driver die het algoritme uitvoert op een uitgewerkt voorbeeld:

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 voor Gierige Drie

Definieer eerst de KnapsackPackage klasse. De __lt__ Met deze methode kan er direct op kosten gesorteerd worden:

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

Voer vervolgens de Fractional Knapsack-routine uit:

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)

Functie knapzakGreProc() in Python

Correctie-opmerking: het origineel Python klasse definieerde een lege __init__ zonder lichaam, wat opheft IndentationErrorDe bovenstaande versie verwijdert de lege constructor omdat die niet nodig is.

De driver die het algoritme uitvoert op het eerste voorbeeld:

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 voor Gierige Drie

Definieer de KnapsackPackage klasse:

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

Implementeer Greedy Three met een stap voor het invullen van fractionele waarden:

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

Functie KnapzakGreProc() in C#

Tegenvoorbeeld: Gierige Drie op 0/1 rugzak

Greedy Three is optimaal voor de fractionele variant, maar op de 0/1 rugzakvariant (waarbij items niet kunnen worden gesplitst) kan deze worden overtroffen. Tegenvoorbeeld:

• Parameters: n = 3, M = 10.
• Pakketten: {i = 1; W = 7; V = 9; kosten = 9/7}, {i = 2; W = 6; V = 6; kosten = 1}, {i = 3; W = 4; V = 4; kosten = 1}.
• Greedy Three kiest pakket 1 voor een totale waarde van 9, terwijl de optimale 0/1-keuze (pakket 2, pakket 3) een waarde van 10 oplevert.

De les: gebruik Greedy Three alleen als breuken zijn toegestaan. Voor de 0/1-variant, gebruik Dynamisch programmeren gebruiken.

Toepassingen van fractionele rugzakken

• Lading waarbij vloeibare, poedervormige of bulkgoederen op gewicht kunnen worden gesplitst.
• Portefeuilleverdeling over beleggingsopties die gedeeltelijke financiering accepteren.
• Bandbreedtedeling in de cloud, waarbij datastromen slechts een fractie van een verbinding kunnen gebruiken.
• CPU-planning volgens een model met gedeelde tijdsslices en deelbare werklasten.
• AI-resourceallocatie waarbij een trainingstaak slechts een fractie van een GPU kan gebruiken.

Veelgestelde vragen