Das Rucksackproblem
Kurz gesagt: Das Rucksackproblem wählt Gegenstände mit dem größten Gesamtwert, ohne ein Gewichtslimit zu überschreiten; eine Tabelle der dynamischen Programmierung aus Gegenständen und Gewicht löst es in O(n · W).
Problem
Welche Pakete in die Kiste kommen
Ein Kurier fährt ein Lastenrad, und seine Kiste trägt bis zu 50 kg. Im Lager warten Pakete. Jedes hat ein Gewicht und eine Liefergebühr, und der Kurier bekommt die Gebühr für jedes gelieferte Paket. Ein Paket lässt sich nicht teilen: Es wird ganz mitgenommen oder gar nicht. Welche Pakete soll der Kurier mitnehmen, um am meisten zu verdienen?
Der Programmierer probiert alles aus: für jedes Paket „mitnehmen“ oder „dalassen“. Sobald jedes Paket entschieden ist, prüft das Programm, ob die Ladung passt und was sie einbringt. Die Pakete kommen aus dem Lager. Hier bauen wir sie mit einer Formel, damit sie in jeder Sprache gleich sind: Gewicht von 1 bis 20 kg, Gebühr von 2 bis 40 €.
static long tries = 0;
static int tryAll(int[] weight, int[] fee, int cap, int i, int load, int sum) { if (i == weight.length) { tries++; return load <= cap ? sum : -1; } int skip = tryAll(weight, fee, cap, i + 1, load, sum); int take = tryAll(weight, fee, cap, i + 1, load + weight[i], sum + fee[i]); return Math.max(skip, take);}
for (int n : new int[] {10, 20}) { int[] weight = new int[n]; int[] fee = new int[n]; for (int i = 0; i < n; i++) { weight[i] = 1 + i * 7 % 20; fee[i] = 2 + i * 11 % 39; } tries = 0; int best = tryAll(weight, fee, 50, 0, 0, 0); System.out.println(n + " Pakete: " + best + " €, " + tries + " Kombinationen");}10 Pakete: 169 €, 1024 Kombinationen20 Pakete: 208 €, 1048576 KombinationenJedes Paket verdoppelt die Kombinationen: 10 Pakete ergeben 1.024, 20 ergeben über eine Million. Bei 30 Paketen sind es über eine Milliarde, und bei 50 Paketen sind es 1.125.899.906.842.624. Bei einer Milliarde Kombinationen pro Sekunde sind das etwa 13 Tage, und der Kurier fährt um acht Uhr morgens los.
Die Idee
Eine Tabelle aus Paketen × Kilogramm
Die Rekursion stellt immer wieder dieselben Fragen: „das Beste ab Paket 7 mit 23 kg Platz“ taucht auf vielen verschiedenen Wegen auf. Speicher für das Paar (Paket, Platz) würde die Wiederholungen beenden. Aber auch hier ist die Tabelle von unten nach oben einfacher, und du kennst sie schon. Nur hat ein Teilproblem diesmal zwei Zahlen: wie viele Pakete du betrachtest und wie viele Kilogramm Platz du hast. Die Tabelle ist zweidimensional.
Die vier Dinge der Tabelle:
- Was eine Zelle bedeutet. best[i][w] ist die höchste Gebühr mit den ersten i Paketen und einer Ladung von höchstens w kg.
- Woher sie kommt. Entweder ist Paket i nicht dabei, dann ist es best[i − 1][w]. Oder es ist dabei: seine Gebühr plus best[i − 1][w − sein Gewicht], das Beste ohne es für die übrigen Kilogramm. Die Zelle behält das Größere.
- In welcher Reihenfolge sie gefüllt wird. Zeile für Zeile: Jede Zeile liest nur die Zeile darüber.
- Wo die Antwort steht. Unten rechts: alle Pakete, die ganze Ladung. Der Start ist Zeile 0, ohne Pakete: überall 0.
Das ist das Rucksackproblem (0/1-Rucksack): Dinge mit Gewicht und Wert, Platz mit einem Limit, und jedes Ding wird ganz genommen oder gar nicht. Es wählt Pakete für eine Tour, Aufgaben für einen Sprint mit begrenzten Stunden, Werbung für begrenzte Sendezeit.
Sieh es dir an
Mitnehmen oder dalassen
Die letzte Tour des Tages: In der Kiste sind noch 6 kg Platz, und vier Pakete warten. Achte auf die zwei Zellen, die jede Zelle liest: die darüber („dalassen“) und den Pfeil aus der Zeile darüber mit der Gebühr („mitnehmen“):
static List<Integer> pack(int[] weight, int[] fee, int cap) { int n = weight.length; int[][] best = new int[n + 1][cap + 1]; for (int i = 1; i <= n; i++) { int kg = weight[i - 1]; int paid = fee[i - 1]; for (int w = 0; w <= cap; w++) { best[i][w] = best[i - 1][w]; if (kg <= w) { int take = best[i - 1][w - kg] + paid; best[i][w] = Math.max(best[i][w], take); } } } List<Integer> taken = new ArrayList<>(); for (int i = n, w = cap; i > 0; i--) { if (best[i][w] != best[i - 1][w]) { taken.add(0, i); w -= weight[i - 1]; } } return taken;}Schritt für Schritt, in Worten
- pack(weight, fee, 6): best[i][w] ist die höchste Gebühr mit den ersten i Paketen und höchstens w kg. Zeile 0 hat keine Pakete, also steht dort nur 0.
- Paket i dalassen: Das Beste bleibt, was die Zeile darüber für dieselben kg hat, best[i − 1][w]. Paket 1 wiegt 4 kg, also ist es unter 4 kg nur das.
- Paket i mitnehmen: seine Gebühr plus das Beste der Zeile darüber für die übrigen kg, best[i − 1][w − kg]. Bei 4 kg: 10 € + 0 = 10 € schlägt 0.
- Zeile 3, 6 kg: Paket 3 (3 kg, 6 €) plus das Beste für 3 kg ohne es, 7 €: 13 € > 10 €. Zwei günstigere Pakete schlagen das teuerste pro kg.
- Zurück von der Ecke unten rechts: Dasselbe wie oben heißt, das Paket wurde dagelassen, anders heißt, es wurde genommen. Paket 4 nicht genommen, Paket 3 genommen, Paket 2 genommen, Paket 1 nicht genommen: 2 + 3 = 13 €.
int[] weight = {4, 3, 3, 1};int[] fee = {10, 7, 6, 2};System.out.println(pack(weight, fee, 6));[2, 3]Die Idee
Welche Pakete
Die Tabelle sagt, wie viel, und der Kurier muss wissen, welche. Die Antwort steckt in der Tabelle selbst. Du beginnst in der Ecke unten rechts. Ist die Zelle gleich der darüber, wird Paket i dafür nicht gebraucht: Du gehst eine Zeile nach oben. Ist sie anders, wurde Paket i genommen: Du gehst eine Zeile nach oben und um sein Gewicht nach links. Und so weiter bis Zeile 0.
Die 20 Pakete von heute und eine Kiste von 50 kg:
static int paid(int[] fee, List<Integer> taken) { int sum = 0; for (int p : taken) { sum += fee[p - 1]; } return sum;}
int[] weight = new int[20];int[] fee = new int[20];for (int i = 0; i < 20; i++) { weight[i] = 1 + i * 7 % 20; fee[i] = 2 + i * 11 % 39;}List<Integer> taken = pack(weight, fee, 50);String list = taken.stream().map(String::valueOf).collect(Collectors.joining(" + "));System.out.println(list + ": " + paid(fee, taken) + " €");1 + 4 + 7 + 8 + 10 + 11 + 13 + 14: 208 €Die Pakete wiegen 48 kg und bringen 208 €, am meisten von allen über einer Million Kombinationen. Die Tabelle hat 20 Paketzeilen mit je 51 Zellen, insgesamt 1.020 Zellen.
Probier es aus
Ergänze
Paket i kommt hinein. Wie viele Kilogramm bleiben für die anderen Pakete?
static List<Integer> pack(int[] weight, int[] fee,
int cap) {
int n = weight.length;
int[][] best = new int[n + 1][cap + 1];
for (int i = 1; i <= n; i++) {
int kg = weight[i - 1];
int paid = fee[i - 1];
for (int w = 0; w <= cap; w++) {
best[i][w] = best[i - 1][w];
if (kg <= w) {
int take = best[i - 1][] + paid;
best[i][w] = Math.max(best[i][w], take);
}
}
}
List<Integer> taken = new ArrayList<>();
for (int i = n, w = cap; i > 0; i--) {
if (best[i][w] != best[i - 1][w]) {
taken.add(0, i);
w -= weight[i - 1];
}
}
return taken;
}Das Paket nimmt kg der w Kilogramm, also bleiben w - kg. Das Beste dafür ohne Paket i steht in der Zeile darüber, in der Spalte w - kg, und ist schon fertig.
Die Idee
Warum nicht das teuerste pro Kilogramm
Es klingt vernünftig: Du rechnest die Gebühr pro Kilogramm jedes Pakets aus und nimmst das teuerste, das passt, dann das nächste. Auf der Tour mit 6 kg kostet Paket 1 2,50 € pro Kilogramm, Paket 2 etwa 2,33, Paket 3 2 und Paket 4 2.
static List<Integer> greedy(int[] weight, int[] fee, int cap) { boolean[] used = new boolean[weight.length]; List<Integer> taken = new ArrayList<>(); while (true) { int pick = -1; double rate = 0; for (int i = 0; i < weight.length; i++) { double perKg = (double) fee[i] / weight[i]; if (!used[i] && weight[i] <= cap && perKg > rate) { pick = i; rate = perKg; } } if (pick < 0) { return taken; } used[pick] = true; taken.add(pick + 1); cap -= weight[pick]; }}int[] weight = {4, 3, 3, 1};int[] fee = {10, 7, 6, 2};List<Integer> fast = greedy(weight, fee, 6);List<Integer> best = pack(weight, fee, 6);String a = fast.stream().map(String::valueOf).collect(Collectors.joining(" + "));String b = best.stream().map(String::valueOf).collect(Collectors.joining(" + "));System.out.println("nach €/kg: " + a + " = " + paid(fee, fast) + " €");System.out.println("Tabelle: " + b + " = " + paid(fee, best) + " €");nach €/kg: 1 + 4 = 12 €Tabelle: 2 + 3 = 13 €Paket 1 kommt zuerst hinein und nimmt 4 kg. Es bleiben 2 kg, und nur Paket 4 passt hinein. Die Pakete 2 und 3 hätten die 6 kg ganz gefüllt und mehr eingebracht. Die Regel wählt, ohne zurückzuschauen, und ihre erste Wahl schließt die bessere Kombination aus. Die Tabelle probiert für jedes Paket und jede Menge Platz beide Möglichkeiten aus.
Könnte man Pakete zerschneiden (Sand, Treibstoff), wäre „das teuerste pro Kilogramm zuerst“ richtig. Wann eine solche Regel funktioniert und wann sie scheitert, ist die Lektion „Wann ein gieriger Algorithmus scheitert“.
Die Idee
Eine Zeile statt einer Tabelle
Jede Zeile liest nur die Zeile darüber. Du brauchst also nicht die ganze Tabelle: Eine Zeile best[0..W] reicht, Paket für Paket überschrieben. Wenn nur die Summe gebraucht wird, wird das Programm kürzer:
static int bestFee(int[] weight, int[] fee, int cap) { int[] best = new int[cap + 1]; for (int i = 0; i < weight.length; i++) { for (int w = cap; w >= weight[i]; w--) { int take = best[w - weight[i]] + fee[i]; best[w] = Math.max(best[w], take); } } return best[cap];}int[] weight = {4, 3, 3, 1};int[] fee = {10, 7, 6, 2};System.out.println(bestFee(weight, fee, 6) + " €");13 €Wichtig ist die Richtung: Die Kilogramm laufen von oben nach unten, von W bis zum Gewicht des Pakets. Zelle w liest best[w − Gewicht], das links von ihr liegt. Von oben nach unten ist diese Zelle in dieser Runde noch nicht überschrieben, stammt also aus der Zeile darüber, ohne das aktuelle Paket. So kommt das Paket höchstens einmal hinein.
Probier es aus
Sag die Ausgabe voraus
5 kg Platz und drei Pakete: 2 kg für 3 €, 3 kg für 4 €, 4 kg für 5 €. Was gibt das Programm aus?
static int bestFee(int[] weight, int[] fee, int cap) { int[] best = new int[cap + 1]; for (int i = 0; i < weight.length; i++) { for (int w = cap; w >= weight[i]; w--) { int take = best[w - weight[i]] + fee[i]; best[w] = Math.max(best[w], take); } } return best[cap];}
int[] weight = {2, 3, 4};int[] fee = {3, 4, 5};System.out.println(bestFee(weight, fee, 5) + " €");Die Pakete 1 und 2 wiegen genau 5 kg und bringen 7 €. Paket 3 ist das teuerste, aber allein bringt es 5 €, und mit Paket 1 sind es 6 kg, was nicht passt. 8 € ist genau dieses unmögliche Paar.
Probier es aus
Finde den Fehler
Ein Kollege hat die Richtung der Kilogramm umgedreht. Für die Tour mit 6 kg sagt sein Programm:
int[] weight = {4, 3, 3, 1};int[] fee = {10, 7, 6, 2};System.out.println(bestFee(weight, fee, 6) + " €");14 €Und das Beste sind 13 €. In welcher Zeile steckt der Fehler?
Wähle die Zeile mit dem Fehler.
Die Kilogramm laufen von unten nach oben. Wenn Zelle w best[w − Gewicht] liest, wurde sie in derselben Runde schon überschrieben, mit diesem Paket darin. Paket 2 (3 kg, 7 €) kommt also in 3 kg hinein und dann noch einmal in 6 kg: 7 + 7 = 14 €. Von oben nach unten stammt die Zelle links noch aus der vorigen Runde, und jedes Paket kommt höchstens einmal hinein.
Sieh es dir an
Miss es: jede Kombination gegen die Tabelle
Wir zählen die geprüften Kombinationen und die Vergleiche „mitnehmen oder dalassen“ in der Zeile. Die Kiste hat 50 kg. Über 20 Paketen werden die Kombinationen nicht ausgeführt: Es sind genau 2ⁿ, also ist die Schätzung mit „≈“ exakt.
- Jede Kombination
O(2ⁿ) - Tabelle (bis 50 kg)
O(n)
| Algorithmus | n = 10 | n = 20 | n = 30 | n = 40 |
|---|---|---|---|---|
| Jede Kombination | 1.024 | 1.048.576 | ≈ 1.073.741.824 | ≈ 1.099.511.627.776 |
| Tabelle (bis 50 kg) | 425 | 810 | 1.235 | 1.620 |
static int bestFee(int[] weight, int[] fee, int cap) { int[] best = new int[cap + 1]; for (int i = 0; i < weight.length; i++) { for (int w = cap; w >= weight[i]; w--) { int take = best[w - weight[i]] + fee[i]; best[w] = Math.max(best[w], take); } } return best[cap];}Jedes neue Paket verdoppelt die Kombinationen und fügt der Tabelle eine Zeile hinzu: höchstens 50 Vergleiche. Bei 40 Paketen macht die Tabelle 1.620 Vergleiche, während die Kombinationen über eine Billion sind. Deshalb wächst die Tabelle auch geradlinig: Bei festen 50 kg ist sie O(n). Den Preis von W erklärt „Genauer“ weiter unten.
Genauer, für Neugierige
Dieselben Zahlen in deiner Sprache:
static long tries = 0;
static int tryAll(int[] weight, int[] fee, int cap, int i, int load, int sum) { if (i == weight.length) { tries++; return load <= cap ? sum : -1; } int skip = tryAll(weight, fee, cap, i + 1, load, sum); int take = tryAll(weight, fee, cap, i + 1, load + weight[i], sum + fee[i]); return Math.max(skip, take);}
static int bestFee(int[] weight, int[] fee, int cap) { int[] best = new int[cap + 1]; for (int i = 0; i < weight.length; i++) { for (int w = cap; w >= weight[i]; w--) { tries++; int take = best[w - weight[i]] + fee[i]; best[w] = Math.max(best[w], take); } } return best[cap];}
for (int n : new int[] {10, 20}) { int[] weight = new int[n]; int[] fee = new int[n]; for (int i = 0; i < n; i++) { weight[i] = 1 + i * 7 % 20; fee[i] = 2 + i * 11 % 39; } tries = 0; tryAll(weight, fee, 50, 0, 0, 0); long all = tries; tries = 0; bestFee(weight, fee, 50); System.out.println(n + " Pakete: Kombinationen " + all + ", Tabelle " + tries);}10 Pakete: Kombinationen 1024, Tabelle 42520 Pakete: Kombinationen 1048576, Tabelle 810Übung
Die Tour aus der Eingabe
Löse die Aufgabe in deinem Editor.
Tour. Lies in der ersten Zeile die Ladung in kg, in der zweiten die Gewichte der Pakete und in der dritten die Gebühren ein. Gib aus, welche Pakete der Kurier mitnehmen soll und wie viel das einbringt. Nutze pack und paid aus der Lektion.
155 6 3 4 7 211 14 6 9 15 31 + 2 + 4: 34 €Weitere Aufgaben
- Und wie viele kg. Gib auch aus, wie viel die mitgenommenen Pakete wiegen und wie viel Platz übrig bleibt.
- Eilige Pakete. Paket 2 muss auf jeden Fall raus. Wie bringst du das ins Problem, ohne eine neue Tabelle zu schreiben? (Tipp: Nimm es von der Liste und senke die Ladung um sein Gewicht.)
- Zwei Kisten. Das Rad hat zwei Kisten zu 25 kg. Warum reicht es nicht, das Problem für 50 kg zu lösen?
Genauer
Genauer: der Preis von W
Warum „O(n · W)“ nicht „immer schnell“ heißt.
Genauer, für Neugierige
Pseudopolynomielle Zeit. Die Tabelle hat n · W Zellen. n ist die Anzahl der Pakete, aber W ist der Wert der Kapazität, nicht die Anzahl der Dinge in der Eingabe. Sind die Gewichte in Gramm, wird aus der 50-kg-Kiste W = 50.000, und die Tabelle ist tausendmal größer. Ist die Kapazität eine Milliarde (Bytes auf einer Festplatte, Cent in einem Budget), passt die Tabelle nicht in den Speicher, bei gleicher Anzahl Pakete. Eine Laufzeit, die ein Polynom in n und im Wert von W ist, aber nicht in der Länge von W in Ziffern, heißt pseudopolynomiell. Jede zusätzliche Ziffer in W multipliziert die Arbeit mit 10. Deshalb ist bei riesigem W und wenigen Paketen das Ausprobieren von Kombinationen mit gutem Abschneiden manchmal schneller.
Speicher. Die ganze Tabelle sind (n + 1) · (W + 1) Zahlen, eine Zeile W + 1. Aber die Zeile allein sagt nicht, welche Pakete: Der Weg zurück braucht alle Zeilen oder wenigstens ein „genommen“-Bit für jede Zelle.
Wenn es unbegrenzt Pakete gibt. Gibt es von jeder Sorte beliebig viele (Wasserkisten zu 6 kg, jede für 4 €), ist „von oben nach unten“ jetzt falsch, und „von unten nach oben“ ist genau das, was du brauchst: Jede Sorte darf noch einmal hinein. Es ist dieselbe Schleife wie beim Wechselgeld, wo jede Münze viele Male benutzt werden darf. Der Fehler aus „Finde den Fehler“ ist die richtige Lösung eines anderen Problems.
Test