0/1-Rucksackproblem (DP)

Wähle Gegenstände mit maximalem Gesamtwert, ohne die Kapazität zu überschreiten. Jede Zeile ist ein eigener Gegenstand, der höchstens einmal gewählt wird. Gewicht,Wert durch Komma, Semikolon oder Leerzeichen trennen. Leerzeilen und Zeilen mit # am Anfang werden ignoriert.

Gewichte und Kapazität verwenden dieselbe frei gewählte Einheit. Dieses Lernwerkzeug erlaubt Kapazität und Gewichte 0–40, höchstens 12 Gegenstände und ganze nichtnegative Werte bis 1000000. Gewicht null ist erlaubt; gleiche Gegenstände sind getrennte Exemplare.

Die DP-Tabelle zeigt den besten Wert mit den ersten i Gegenständen bei Kapazität c. Jede Zelle vergleicht Weglassen mit Aufnehmen plus der vorherigen Zeile bei c−Gewicht. Der markierte Pfad verfolgt die Auswahl; bei Gleichstand bleibt die frühere Auswahl. Minimales Gewicht oder sämtliche optimalen Lösungen werden nicht garantiert.

Die Berechnung erfolgt sofort und benötigt O(n × (Kapazität + 1)) Zeit und Speicher für n Gegenstände. Änderungen entfernen alte Ergebnisse; Zurücksetzen stellt das Beispiel wieder her. Rohwerte und Kommentare bleiben lokal in diesem Browser erhalten, auch unvollständige Kapazitätseingaben. Nach Neuladen erneut berechnen. Ältere gespeicherte oder geteilte Beispiele bleiben unterstützt. Überschreitet ein Entwurf die lokale Speichergrenze, erscheint ein Hinweis: Text vor dem Verlassen kopieren. Die vorherige gespeicherte Fassung bleibt erhalten.