Rucksackproblem

Problem der Kombinatorik zur Optimierung der Ressourcennutzung
(Weitergeleitet von Knapsack-Problem)

Das Rucksackproblem (auch englisch knapsack problem) ist ein Optimierungsproblem der Kombinatorik. Aus einer Menge von Objekten, die jeweils ein Gewicht und einen Nutzwert haben, soll eine Teilmenge ausgewählt werden, deren Gesamtgewicht eine vorgegebene Gewichtsschranke nicht überschreitet. Unter dieser Bedingung soll der Nutzwert der ausgewählten Objekte maximiert werden.

Das Rucksackproblem: Welche der Gewichte können in den Rucksack mit Maximallast von 15 kg gepackt werden, so dass der Geldwert maximal wird? (Lösung in diesem Fall: Alle Gewichte außer dem schwersten einpacken.)

Die Entscheidungsvariante des Rucksackproblems fragt, ob ein zusätzlich vorgegebener Nutzwert erreicht werden kann. Sie gehört zur Liste der 21 klassischen NP-vollständigen Probleme, von denen Richard Karp 1972 die Zugehörigkeit zu dieser Klasse zeigen konnte.[1]

In der Kryptographie wird häufig eine andere Entscheidungsvariante betrachtet. Dabei werden nur die Gewichte betrachtet und es wird gefragt, ob es eine Teilmenge der Objekte gibt, die einen vorgegebenen Gewichtswert genau erreicht. Diese Problemvariante wird auch als SUBSET-SUM bezeichnet. Basierend auf dieser Variante wurde das Public-Key-Kryptoverfahren Merkle-Hellman-Kryptosystem entwickelt, das sich allerdings als nicht besonders sicher herausstellte.

Anschauung

Bearbeiten

Das Rucksackproblem hat seinen Namen aus folgender Anschauung heraus erhalten: Es sind verschiedene Gegenstände mit einem bestimmten Gewicht und einem Nutzwert gegeben. Aus diesen Gegenständen soll nun eine Auswahl getroffen werden, die in einen Rucksack mit einer vorgegebenen Gewichtsschranke mitgenommen werden können. In der Literatur wird zur Veranschaulichung auch gerne der Dieb herangezogen, der nur einen kleinen Teil der Beute im Rucksack abtransportieren kann und nun versucht, das Maximum an Nutzwert herauszuschlagen.

Mathematische Formulierung

Bearbeiten

Gegeben ist eine endliche Menge von Objekten  . Durch eine Gewichtsfunktion   und die Nutzenfunktion   wird den Objekten ein Gewicht und ein festgelegter Nutzwert zugeordnet:

 
 

Des Weiteren gibt es eine vorgegebene Gewichtsschranke  .

Gesucht ist eine Teilmenge  , die die Bedingung

  einhält und die Zielfunktion   maximiert.

Der Spezialfall   führt auf das Teilsummenproblem.

Lösung durch dynamische Programmierung

Bearbeiten

Sind die Gewichte ganzzahlig, so lässt sich der optimale Wert des Rucksackproblems auch mittels dynamischer Programmierung lösen. Seien dazu   die Elemente von  .

Eingabe: U, B, w, v wie oben beschrieben
  R := [1…(n+1), 0…B]-Matrix, mit Einträgen 0
  FOR i = n … 1
    FOR j = 1 … B
      IF w(i) <= j
        R[i,j] := max( v(i) + R[i+1, j-w(i)], R[i+1,j] )
      ELSE
        R[i,j] := R[i+1,j]
Ausgabe: R[1,B]

In jeder Speicherzelle   ist der maximale Nutzwert bei maximal möglichem Gesamtgewicht von   bei Berücksichtigung einer Teilmenge von Gegenständen aus der Teilsequenz   der Gesamtsequenz aller Gegenstände  . Also ist der maximale Nutzwert bei Berücksichtigung einer Teilmenge aller Gegenstände in der Zelle   nach Beendigung des Algorithmus gespeichert.

In jeder Zeile   der Matrix   wird über die beiden Fälle optimiert, ob der Nutzwert maximal vergrößert werden kann, wenn der Gegenstand   mit dem Gewicht   dem Rucksack hinzugefügt oder er nicht aufgenommen wird. Im ersten Fall erhöht sich der Nutzwert um  .

Um den Inhalt des Rucksacks mit dem maximalen Nutzwert zu bestimmen, kann er rekonstruiert werden, indem die Berechnung des Optimums in   mittels Backtracking zurückverfolgt wird.

Die Korrektheit folgt aus der folgenden Beobachtung:

Sei   eine optimale Lösung. Dann ist   eine optimale Lösung für die Instanz   mit Maximalgewicht  . Der Algorithmus benötigt aufgrund der verschachtelten for-Schleifen, die über n und B iterieren, eine Laufzeit von  . Hierbei ist zu beachten, dass B eine zu seiner Eingabelänge exponentiell wachsende Größe und somit die Laufzeit pseudopolynomiell ist.

Das folgende Beispiel zeigt eine Implementierung des Algorithmus in der Programmiersprache C++.[2]

#include <iostream>
using namespace std;

// Diese Funktion prüft, ob es eine Aufteilung der Menge mit gleichen Summen gibt und gibt dann true zurück, sonst false
bool findPartition(int numbers[], int n)
{
    int sum = 0;
    for (int i = 0; i < n; i++) // for-Schleife, die die Summe der Zahlen berechnet
    {
        sum += numbers[i];
    }
    if (sum % 2 != 0) // Wenn die Summe ungerade ist, wird false zurückgegeben
    {
        return false;
    }
    bool* part = new bool[sum / 2 + 1]; // Deklariert ein Array, in dem gespeichert wird, ob die Zahlen 0, 1, 2, ... als Summe einer Teilmenge der gegebenen Zahlen dargestellt werden können
    for (int i = 0; i <= sum / 2; i++) // for-Schleife, die das Array initialisiert
    {
        part[i] = false;
    }
    for (int i = 0; i < n; i++) // for-Schleife, die die Indexe der Zahlen durchläuft
    {
        for (int j = sum / 2; j >= numbers[i]; j--) // In dieser for-Schleife wird geprüft, ob Halbe Gesamtsumme - Zahl mit Index i als Summe einer Teilmenge von Zahlen mit Index kleiner als i dargestellt werden kann
        {
            if (part[j - numbers[i]] || j == numbers[i]) // Wenn die Summe j - Zahl mit Index i dargestellt werden kann oder die Zahl mit Index i gleich j ist, wird das Element für die Summe j auf true gesetzt
            {
                part[j] = true;
            }
        }
    }
    return part[sum / 2]; // Gibt das Element für die halbe Gesamtsumme der Zahlen zurück. Dieses Element vom Typ bool gibt an, ob diese Summe dargestellt werden kann.
}

// Hauptfunktion die das Programm ausführt
int main()
{
    int numbers[] = { 1, 3, 3, 2, 3, 2 };
    int n = sizeof(numbers) / sizeof(numbers[0]); // Variable für die Anzahl der Zahlen
    if (findPartition(numbers, n)) // Wenn eine Aufteilung mit gleichen Summen gefunden wurde
    {
        cout << "Es gibt eine Aufteilung mit gleichen Summen." << endl; // Ausgabe auf der Konsole
    }
    else
    {
        cout << "Es gibt keine Aufteilung mit gleichen Summen." << endl; // Ausgabe auf der Konsole
    }
}

Lösung mittels Profitabilitätsindex

Bearbeiten

In der Praxis wird ein Ranking der Objekte nach Profitabilitätsindex vorgenommen:

 

  • PI = Profitabilitätsindex
  • W = Generierter Wert (hier: Nutzwert)
  • R = Verbrauchte Ressourcen (hier: Gewicht)

Dann werden möglichst viele Objekte gewählt, beginnend mit dem Objekt mit höchstem Profitabilitätsindex. Dies führt bei ganzzahligen Problemen nicht immer zur optimalen Lösung, ist aber sehr praktikabel. Bei dieser Methodik handelt es sich um einen Greedy-Algorithmus.

Lösung mittels ganzzahliger linearer Optimierung

Bearbeiten

Das Rucksackproblem lässt sich wie folgt als ganzzahliges lineares Optimierungsproblem (integer linear program oder kurz ILP) formulieren. Sei dazu   für jedes Element   eine binäre Entscheidungsvariable mit der folgenden Interpretation:

  •  : Das Element   wird im Rucksack mitgenommen.
  •  : Das Element   wird nicht im Rucksack mitgenommen.

Dies führt zu folgender Modellierung des Rucksackproblems

 ,

welches mit gängigen kommerziellen und nichtkommerziellen Solvern wie etwa CPLEX, Gurobi, FICO Xpress, SCIP, GLPK und CBC auch für große praxisrelevante Instanzen global optimal gelöst werden kann.[3]

Anwendungen

Bearbeiten

Viele reale Situationen lassen sich mit Hilfe der Lösung dieses Problems mathematisch klären. Oft steht eine begrenzte Kapazität zur Verfügung, welche nicht die gesamte Nachfrage befriedigen kann. Man denke z. B. an einen Lkw, der viele verschiedene Güter – mit einem bestimmten Gewinn – transportieren soll, aber wegen der begrenzten Lademenge nicht alle Güter aufnehmen kann. Der Besitzer des Lkws wird die Ladung so wählen wollen, dass der Gewinn maximal ausfällt.

Siehe auch

Bearbeiten

Literatur

Bearbeiten
Bearbeiten

Einzelnachweise

Bearbeiten
  1. Richard M.Karp: Reducibility Among Combinatorial Problems. In: Springer (Hrsg.): Proceedings of a symposium on the Complexity of Computer Computations. Yorktown Heights, New York 1972, S. 85–103 (amerikanisches Englisch, springer.com).
  2. GeeksforGeeks: 0-1 Knapsack Problem (englisch)
  3. David Pisinger: Where are the hard knapsack problems? In: Computers & Operations Research. Band 32, Nr. 9, September 2005, ISSN 0305-0548, S. 2271–2284, doi:10.1016/j.cor.2004.03.002 (englisch, gla.ac.uk [PDF; abgerufen am 4. Dezember 2023]).