Fractional Knapsack Problem: girig algoritm med exempel

Vad är Greedy Strategy?

Giriga algoritmer Välj det bästa lokala valet i varje steg i hopp om att en kedja av lokala optima producerar en globalt optimal lösning. Liksom dynamisk programmering riktar de in sig på optimeringsproblem, men de ser aldrig tillbaka för att ompröva tidigare beslut.

Giriga algoritmer är vanligtvis enkla att skriva, snabba (ofta linjär eller kvadratisk tid), lätta att felsöka och kräver lite minne. Nackdelen är att resultatet inte alltid är optimalt, så strategin fungerar bara för problem som har en bevisad girig-säker struktur.

Giriga strategier löser kombinatorisk optimering genom att bygga en lösning A, en komponent av AI i taget. Vid varje steg väljer du AI optimalt under de rådande begränsningarna och krymper problemet till ett mindre delproblem.

Två egenskaper måste gälla för att en girig metod ska vara korrekt:

1. Girigt val egendom: Ett lokalt optimum i varje steg leder till ett globalt optimum. Valet beror på tidigare beslut men inte på framtida.
2. Optimal underkonstruktion: Den optimala lösningen av hela problemet innehåller optimala lösningar av dess delproblem.

En girig algoritm har fem komponenter:

1. En kandidatuppsättning från vilken lösningar byggs.
2. En urvalsfunktion som väljer den bästa nästa kandidaten.
3. En genomförbarhetsfunktion som kontrollerar om en kandidat kan utöka den aktuella partiella lösningen.
4. En objektivfunktion som värderar en fullständig eller partiell lösning.
5. En utvärderingsfunktion som signalerar när lösningen är klar.

Idén om girig

Greedy One sorterar paket enbart efter värde:

• Sortera paket i icke-stigande värdeordning.
• Gå igenom den sorterade listan och lägg varje paket i ryggsäcken om den återstående kapaciteten rymmer det.

Denna regel ger inte alltid det optimala svaret. Motexempel:

• Parametrar: n = 3, M = 19.
• Paket: {i = 1; W = 14; V = 20}, {i = 2; W = 6; V = 16}, {i = 3; W = 10; V = 8} — högt värde men också hög vikt.
• Den girige väljer paket 1 med ett totalt värde på 20, medan det optimala valet (paket 2, paket 3) når 24.

Idén om giriga två

Greedy Two sorterar paket enbart efter vikt:

• Sortera paketen i icke-fallande viktordning.
• Gå igenom den sorterade listan och lägg varje paket i ryggsäcken om den återstående kapaciteten rymmer det.

Denna regel misslyckas också med att vara optimal. Motexempel:

• Parametrar: n = 3, M = 11.
• Paket: {i = 1; W = 5; V = 10}, {i = 2; W = 6; V = 16}, {i = 3; W = 10; V = 28} — låg vikt men lågt värde.
• Giriga Två val (paket 1, paket 2) med totalt värde 26, medan det optimala valet (paket 3) når 28.

Idén om giriga tre

Greedy Three åtgärdar båda felen genom att kombinera värde och vikt i en enda rangordningsnyckel. Det är standardmetoden för det bråkdelsbaserade ryggsäcksproblemet.

• Beräkna enhetskostnaden V[i] / W[i] för varje paket.
• Sortera paket i icke-stigande ordning efter enhetskostnad.
• Gå igenom den sorterade listan och lägg till varje paket om den återstående kapaciteten rymmer det.

Giriga Tre sorteringar efter enhetskostnad V[i] / W[i]

Idé: Beräkna vikt-värde-förhållandet V[i] / W[i] för varje paket, sortera i fallande ordning och ta det största tillgängliga förhållandet först tills ryggsäcken är full.

För det sanna Fraktionerad variant, när nästa paket inte får plats helt, ta en bråkdel som exakt fyller den återstående kapaciteten. Den extra regeln är det som gör Greedy Three bevisligen optimal på Fractional Knapsack.

Steg i algoritmen

För 0/1-varianten med gren och bundna punkter driver den sorterade enhetskostnadslistan ett sökträd:

• Steg 1: Rotnoden representerar en tom ryggsäck. TotalValue = 0. UpperBound = M × maximal enhetskostnad.
• Steg 2: Förgrena roten efter hur många kopior av paketet med största förhållandet som får plats. För varje barn, beräkna om TotalValue, återstående kapacitet M och UpperBound.
• Steg 3: Utöka barnet med den största övre gränsen först, i hopp om att snabbt hitta en stark lösning.
• Steg 4: Beskär alla noder vars UpperBound inte är bättre än den nuvarande bästa kompletta lösningen.
• Steg 5: När varje nod antingen utökas eller beskärs är den nuvarande bästa kompletta lösningen optimal.

Pseudokod för den rena fraktionella ryggsäcksgiriga algoritmen:

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

Algoritmens komplexitet:

• Med en enkel sortering (urval eller bubbla): O(n²).
• Användning av snabb sortering eller sammanslagningssortering: O(n log n), dominerad av sorteringssteget.

Java Code för giriga tre

Definiera KnapsackPackage klass med vikt, värde och härledd kostnad (V/W-förhållandet som används för 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; }
}

Skapa sedan funktionen som implementerar 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);
}

Funktion knapsackGreProc() in Java

Förklaring av kod:

1. Slå in varje inmatning i en KnapsackPackage så sorteringsnyckeln (V/W-förhållandet) är förberäknad.
2. Sortera i fallande kostnadsordning.
3. Ta varje paket hel om det får plats.
4. Ta en bråkdel av nästa paket för att fylla den överblivna kapaciteten.
5. Stoppa så snart den återstående kapaciteten når noll.

Åtgärdsanmärkning: ursprungliga Java loop avancerad i endast när ett paket inte fick plats, vilket orsakade att samma paket togs upprepade gånger. Versionen ovan flyttar fram ett paket per iteration och lägger till ett steg för fraktionerad fyllning, vilket matchar den sanna regeln för fraktionerad ryggsäck.

Java drivrutin som kör algoritmen på ett fungerande exempel:

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 för giriga tre

Definiera först KnapsackPackage klass. De __lt__ Metoden gör det direkt sorterbart efter kostnad:

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

Implementera sedan Fractional Knapsack-rutinen:

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)

Funktion knapsackGreProc() in Python

Åtgärdsanmärkning: ursprungliga Python klassen definierade en tom __init__ utan kropp, som höjer IndentationErrorVersionen ovan tar bort den tomma konstruktorn eftersom ingen behövs.

Drivrutin som kör algoritmen i det första exemplet:

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 för giriga tre

Definiera KnapsackPackage klass:

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

Implementera Greedy Three med ett steg med fraktionerad fyllning:

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

Funktion KnapsackGreProc() i C#

Motexempel: Giriga tre på 0/1 ryggsäck

Giriga Tre är optimal för Bråkvarianten, men på 0/1 Ryggsäcken (där föremål inte kan delas) kan den besegras. Motexempel:

• Parametrar: n = 3, M = 10.
• Paket: {i = 1; W = 7; V = 9; kostnad = 9/7}, {i = 2; W = 6; V = 6; kostnad = 1}, {i = 3; W = 4; V = 4; kostnad = 1}.
• Greedy Three väljer paket 1 för totalt värde 9, medan det optimala 0/1-valet (paket 2, paket 3) når 10.

Lärdomen: använd Greedy Three endast när bråk är tillåtna. För 0/1-varianten, använd Dynamisk programmering istället.

Tillämpningar av fraktionerad ryggsäck

• Lastning där flytande, pulveriserade eller bulkgods kan delas upp efter vikt.
• Portföljallokering över investeringsalternativ som accepterar delfinansiering.
• Molnbandbreddsdelning där flöden kan förbruka en bråkdel av en länk.
• CPU-schemaläggning under en delad tidssegmentmodell med delbara arbetsbelastningar.
• AI-resursallokering där ett utbildningsjobb kan använda en bråkdel av en GPU.

Vanliga frågor