Rucksackproblem

[AtTheDriveIn]

Hi

Ich sitz hier gerade vor dem Rucksackproblem. Ich habe es auch mittels dynamischer Programmierung soweit gelöst, das die Wertetabelle richtig ausgefüllt wird. Ich bekomme somit jeden optimalen Wert W aus einer Anzahl k von Pakten für einen Rucksack der Größe g.

Was mir jetzt noch fehlt ist die optimale Packung auszugeben. Unser Prof meint, das könne man ohne eine zusätzliche Tabelle aus der Kapazität g und den Werten in der Tabelle ausrechnen können, nur wie?

Ich habe im Internet bisher keine Lösung gefunden...

[Trap]

Dazu macht man im Grunde das gleiche, nur rückwärts. Bei der optimalen Lösung anfangen und probieren jedes mögliche Ding wieder wegzunehmen, wenn dabei genau das rauskommt was in der Tabelle steht, dann war das Ding dabei.

[aths]

Ich habe im Internet bisher keine Lösung gefunden...Wäre ja auch zu schön, wenn alles im Internet stünde ...?

Das Rucksackproblem löste ich typisch aths: Das Programm ist langsam und verballert Unmengen Speicher – aber es funktioniert.

Zunächst werden alle Möglichkeiten den Rucksack zu füllen (ohne ihn zu überfüllen) ausprobiert und das Ergebnis in eine Liste geschrieben. Dann wird die Liste auf ihr Maximum untersucht und anschließend werden in einem weiteren Durchlauf alle Maxima ausgegeben. Der Prof sagte erst später, dass ihm eine optimale Lösung genügt hätte. Trotzdem gabs volle Punktzahl =)

[Coda]

Das ist doch NP-vollständig, geht also gar nicht "schnell".

[Senior Sanchez]

In diesem Zusammenhang scheint es aber um ein spezielleres Rucksackproblem mit stark begrenztem Fassungsvermögen und Auflagen an die Pakete zu gehen. Das ist durchaus schnell mittels DP lösbar. Das allgemeine Rucksackproblem wie ich es jetzt mal nenne, ist dagegen NP.

[Trap]

Es gibt bei NP-Problemen meistens viele Spezialfälle die effizient lösbar sind.

Rucksackproblem mit kleiner Rucksackgröße, das Färbungsproblem in zyklenfreien Graphen, usw...
Auch hängt die Schwierigkeit stark von den tatsächlich verwendeten Eingaben ab, das allgemeine boolsche Erfüllbarkeitsproblem ist NP-vollständig, trotzdem sind sehr viele Probleminstanzen die praktisch vorkommen schnell lösbar, siehe http://satlive.org/

[AtTheDriveIn]

Wäre ja auch zu schön, wenn alles im Internet stünde ...?

Das Rucksackproblem löste ich typisch aths: Das Programm ist langsam und verballert Unmengen Speicher – aber es funktioniert.

Zunächst werden alle Möglichkeiten den Rucksack zu füllen (ohne ihn zu überfüllen) ausprobiert und das Ergebnis in eine Liste geschrieben. Dann wird die Liste auf ihr Maximum untersucht und anschließend werden in einem weiteren Durchlauf alle Maxima ausgegeben. Der Prof sagte erst später, dass ihm eine optimale Lösung genügt hätte. Trotzdem gabs volle Punktzahl =)


Wenn du das Rucksackproblem mittels dynamischer Programmierung löst, dann mußt du keine Maxima mehr suchen. Es steht in der Wertetabelle an Position [letztes_Element][größtes_Gewicht] ;)

Viel Speicher braucht die dyn. Programmierung sicherlich auch, weil du eben alle Teilkombinationen löst, dafür ist sie im Vergleich mit deiner Brute Force Methode sehr schnell.

Um mein Programm etwas Speicherfreundlicher zu machen, habe ich auf die Referenztabelle ja bewußt verzichten wollen(nur darum ging es in diesem Thread), sie ist nämlich eigentlich überflüssig.

Ziel der Aufgabe war es. Einen Rucksack g=1000 mit n=268 Elementen zu füllen.

O(n*g) bei dynamischer Prog.
O(2^n) bei Brute Force