Fractional Knapsack Problem: Gieriger Algorithmus mit Beispiel

Was ist eine Greedy-Strategie?

Gierige Algorithmen Sie wählen in jedem Schritt die beste lokale Option in der Hoffnung, dass eine Kette lokaler Optima zu einer global optimalen Lösung führt. Ähnlich wie die dynamische Programmierung zielen sie auf Optimierungsprobleme ab, ohne jedoch frühere Entscheidungen rückwirkend zu überdenken.

Greedy-Algorithmen sind in der Regel einfach zu implementieren, schnell (oft linear oder quadratisch), leicht zu debuggen und speicherschonend. Der Nachteil ist, dass das Ergebnis nicht immer optimal ist; daher eignet sich diese Strategie nur für Probleme mit einer nachweislich greedy-sicheren Struktur.

Greedy-Strategien lösen kombinatorische Optimierungsprobleme, indem sie eine Lösung A schrittweise, Komponente Ai, aufbauen. In jedem Schritt wird Ai unter den gegebenen Nebenbedingungen optimal gewählt und das Problem auf ein kleineres Teilproblem reduziert.

Zwei Eigenschaften müssen erfüllt sein, damit eine Greedy-Methode korrekt ist:

1. Grey-Choice-Eigenschaft: Ein lokales Optimum in jedem Schritt führt zu einem globalen Optimum. Die Wahl hängt von vergangenen Entscheidungen ab, nicht aber von zukünftigen.
2. Optimale Teilstruktur: Die optimale Lösung des Gesamtproblems enthält optimale Lösungen seiner Teilprobleme.

Ein Greedy-Algorithmus besteht aus fünf Komponenten:

1. Ein Kandidatensatz, aus dem Lösungen entwickelt werden.
2. Eine Auswahlfunktion, die den besten nächsten Kandidaten auswählt.
3. Eine Machbarkeitsfunktion, die prüft, ob ein Kandidat die aktuelle Teillösung erweitern kann.
4. Eine Zielfunktion, die eine vollständige oder partielle Lösung bewertet.
5. Eine Auswertungsfunktion, die signalisiert, wann die Lösung abgeschlossen ist.

Die Idee des Gierigen

Greedy One sortiert Pakete ausschließlich nach Wert:

• Sortieren Sie die Pakete in absteigender Reihenfolge ihres Wertes.
• Gehe die sortierte Liste durch und füge jedes Paket dem Rucksack hinzu, sofern der verbleibende Platz dies zulässt.

Diese Regel liefert nicht immer die optimale Lösung. Gegenbeispiel:

• Parameter: n = 3, M = 19.
• Pakete: {i = 1; W = 14; V = 20}, {i = 2; W = 6; V = 16}, {i = 3; W = 10; V = 8} — hoher Wert, aber auch hohes Gewicht.
• Der gierige Typ wählt Paket 1 mit einem Gesamtwert von 20, während die optimale Wahl (Paket 2, Paket 3) einen Wert von 24 erreicht.

Die Idee von Greedy Two

Greedy Two sortiert Pakete ausschließlich nach Gewicht:

• Sortieren Sie die Pakete in aufsteigender Reihenfolge ihres Gewichts.
• Gehe die sortierte Liste durch und füge jedes Paket dem Rucksack hinzu, sofern der verbleibende Platz dies zulässt.

Auch diese Regel ist nicht optimal. Gegenbeispiel:

• Parameter: n = 3, M = 11.
• Pakete: {i = 1; W = 5; V = 10}, {i = 2; W = 6; V = 16}, {i = 3; W = 10; V = 28} — geringes Gewicht, aber niedriger Wert.
• Greedy Two wählt (Paket 1, Paket 2) mit einem Gesamtwert von 26, während die optimale Wahl (Paket 3) 28 erreicht.

Die Idee der Greedy Three

Greedy Three behebt beide Probleme, indem es Wert und Gewicht zu einem einzigen Rangordnungsschlüssel kombiniert. Es ist die Standardmethode für das fraktionale Rucksackproblem.

• Berechnen Sie die Stückkosten V[i] / W[i] für jedes Paket.
• Sortieren Sie die Pakete in absteigender Reihenfolge des Stückpreises.
• Gehe die sortierte Liste durch und füge jedes Paket hinzu, sofern die verbleibende Kapazität dies zulässt.

Greedy Three sortiert nach Stückkosten V[i] / W[i]

Idee: Berechne für jedes Paket das Wert-Gewichts-Verhältnis V[i] / W[i], sortiere die Pakete in absteigender Reihenfolge und nimm zuerst das Paket mit dem größten verfügbaren Verhältnis, bis der Rucksack voll ist.

Für das Wahre fraktioniert Eine Variante davon ist, dass, wenn das nächste Paket nicht vollständig hineinpasst, ein Bruchteil genommen wird, der genau die verbleibende Kapazität ausfüllt. Diese zusätzliche Regel macht Greedy Three nachweislich optimal für das Fractional Rnapsack-Problem.

Schritte des Algorithmus

Bei der 0/1-Branch-and-Bound-Variante steuert die sortierte Liste der Einheitskosten einen Suchbaum:

• Schritt 1: Der Wurzelknoten repräsentiert einen leeren Rucksack. Gesamtwert = 0. Obergrenze = M × maximale Stückkosten.
• Schritt 2: Verzweige die Wurzel um die Anzahl der Kopien des Pakets mit dem größten Verhältnis, die hineinpassen. Berechne für jedes Kind den Gesamtwert, die verbleibende Kapazität M und die obere Grenze neu.
• Schritt 3: Erweitere zuerst das Kind mit dem größten UpperBound, in der Hoffnung, schnell eine starke Lösung zu finden.
• Schritt 4: Entferne alle Knoten, deren obere Schranke nicht besser ist als die aktuell beste vollständige Lösung.
• Schritt 5: Wenn jeder Knoten entweder erweitert oder beschnitten wird, ist die aktuell beste Gesamtlösung optimal.

Pseudocode für den reinen fraktionalen Rucksack-Greedy-Algorithmus:

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

Komplexität des Algorithmus:

• Bei Verwendung eines einfachen Sortieralgorithmus (Selektion oder Bubble): O(n)²).
• Bei Verwendung von Quicksort oder Mergesort: O(n log n), wobei der Sortierschritt den größten Teil der Komplexität ausmacht.

Java Code für Greedy Three

Definiere das KnapsackPackage Klasse mit Gewicht, Wert und abgeleiteten Kosten (das für die Sortierung verwendete V/W-Verhältnis):

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

Erstellen Sie anschließend die Funktion, die Greedy Three implementiert:

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

Erklärung des Codes:

1. Verpacken Sie jede Eingabe in ein KnapsackPackage Der Sortierschlüssel (V/W-Verhältnis) wird also vorab berechnet.
2. Sortieren Sie in absteigender Reihenfolge der Kosten.
3. Nehmen Sie jedes Paket im Ganzen mit, sofern es hineinpasst.
4. Nehmen Sie einen Bruchteil der nächsten Packung, um die verbleibende Kapazität auszunutzen.
5. Stoppen Sie, sobald die verbleibende Kapazität Null erreicht.

Korrekturhinweis: das Original Java Schleife erweitert i Nur wenn ein Paket nicht passte, wurde dasselbe Paket wiederholt entnommen. Die obige Version verschiebt in jeder Iteration ein Paket und fügt einen Schritt zur Teilfüllung hinzu, was der eigentlichen Regel des fraktionierten Rucksackproblems entspricht.

Java Treiber, der den Algorithmus anhand eines Beispiels ausführt:

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

Zuerst definieren wir die KnapsackPackage Klasse. Das __lt__ Durch diese Methode ist eine direkte Sortierung nach Kosten möglich:

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

Implementieren Sie anschließend die Routine für den fraktionierten Rucksack:

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

Korrekturhinweis: das Original Python Die Klasse definierte ein leeres __init__ ohne Körper, was aufwirft IndentationErrorDie obige Version entfernt den leeren Konstruktor, da keiner benötigt wird.

Treiber, der den Algorithmus im ersten Beispiel ausführt:

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

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

Implementieren Sie Greedy Three mit einem Schritt zur fraktionalen Füllung:

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() in C#

Gegenbeispiel: Gieriger Dreier auf 0/1 Rucksack

Greedy Three ist optimal für die Fractional-Variante, aber bei der 0/1-Rucksack-Variante (bei der Gegenstände nicht geteilt werden können) kann es geschlagen werden. Gegenbeispiel:

• Parameter: n = 3, M = 10.
• Pakete: {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 wählt Paket 1 für einen Gesamtwert von 9, während die optimale 0/1-Wahl (Paket 2, Paket 3) einen Wert von 10 erreicht.

Die Lektion: Verwenden Sie Greedy Three nur, wenn Brüche erlaubt sind. Für die 0/1-Variante verwenden Sie Dynamische Programmierung stattdessen.

Anwendungen der fraktionalen Rucksacktheorie

• Ladungsverladung, bei der flüssige, pulverförmige oder loser Schüttgut nach Gewicht aufgeteilt werden können.
• Portfolioaufteilung über Anlageoptionen, die eine Teilfinanzierung akzeptieren.
• Bandbreitenteilung in der Cloud, bei der Datenströme nur einen Bruchteil einer Verbindung beanspruchen können.
• CPU-Planung im Rahmen eines Shared-Time-Slice-Modells mit teilbaren Arbeitslasten.
• KI-Ressourcenzuweisung, bei der ein Trainingsvorgang nur einen Bruchteil einer GPU nutzen kann.

Häufig gestellte Fragen