Rucksackproblem als dynamische Programmierung

Nun wird das Rucksackproblem mit dynamischer Programmierung gelöst. Wir erinnern uns, dass das Grundprinzip der dynamischen Programmierung die Wiederverwendung von bereits berechneten Teillösungen ist. Aber an dieser Stelle ist Vorsicht geboten mit den anderen Lösungen aus den vorherigen Seiten, wo Teillösungen Bottom up zusammengesetzt wurden. Hier basieren die Lösungen auf der Backtracking Variante. Teillösungen werden zwischengespeichert. Die Existenz von Teillösungen wird als Abbruchkriterium für die Rekursion verwendet.

Rekursionseinstieg

static Rucksack packeMitDynamischerProgrammierung()
   Rucksack [][] zwischenErgebnisse=
      new Rucksack[kapazitaet+1][anzahlObjekte];
   return rucksackRekursivDP (0, new Rucksack(), zwischenErgebnisse);
}

Ein Eintrag zwischenErgebnisse[g][i] bedeutet, dass wir schon ein mal dabei waren, das Objekt i in einen Rucksack mit dem Gewicht g zu legen. In diesem Fall können wir alle vor berechneten Entscheidungen für die Objekte i bis anzahlObjekte −1 wiederverwenden, da diese bereits optimal sind (Backtracking: äquivalenter Teilbaum).

Rekursion

static Rucksack rucksackRekursivDP (int i, Rucksack r, Rucksack [][] zwischenErgebnisse){
   if (i == auswahlObjekte.length) return r;
   int gewicht = r.gewicht();
   // Wiederverwendung von Teillösungen:
   if (zwischenErgebnisse[gewicht][i] != null}{
      for (int j = i; j < anzahlObjekte; j++)
         r.auswahl[j] = zwischenErgebnisse[gewicht][i].auswahl[j];
      return r;
   }
   Rucksack r1 = new Rucksack (r);
   r1 = rucksackRekursivDP(i+1, r1, zwischenErgbenisse);
   if (gewicht+auswahlObjekte[i].gewicht <= kapazitaet){
      Rucksack r2 = new Rucksack (r);
      r2.auswahl[i] = true;
     
      if (r2.nutzen() > r1.nutzen()) r1 = r2;
   }
   // Merken von Teillösungen:
   zwischenErgebnisse[gewicht][i] = r1;
   return r1;
}

Analyse

Die Vorteile der dynamischen Programmierung sind, dass auf jeden Fall die optimale Lösung gefunden wird. In vielen Fällen hat sie auch einen geringeren Aufwand als Backtracking. Das Problem ist allerdings, dass die Anwendbarkeit und der Aufwand abhängig von der Größe und der Struktur des Suchraums sind. Die Komplexität beträgt O(z), wobei z die Anzahl der möglichen Zwischenergebnisse ist. Zum Beispiel: bei vielen unterschiedlichen Gewichtskombinationen kaum Ersparnis (Erhöhen von MAX_GEWICHT). Außerdem existieren polynomielle Approximationen!