Rucksackproblem / Subset Sum Problem

[toad]

Hallo,
ich hab mal ´ne Frage zu den zwei Problemen oben. Also ich hab gelesen, dass die sich mit dynamischer Programmierung lösen lassen, aber wie.
Beim Rucksackproblem habe ich ja verschieden Gegenstände, die alle einen Nutzwert und einen Gewichtswert haben.

Nun würde ich es so machen (hab es noch nicht ausprobiert), dass ich alle Gegenstände in einer Liste speichere, die unter dem Maximum Gewicht sind, dann speicher ich im nächsten Durchlauf die zweier-Kombinationen, die immer noch unter dem Maximalgewicht sind (wobei ich die einzelnen in der Liste lassse, sie könnten ja teil einer besten Lösung sein).
Das mache ich bis ich soviele Durchläufe lang wie es insgesamt Gegenstände gibt.
Aber wie kann man das jetzt durch dynamische Programmierung erleichtern, richtige Zwischen ergebnisse (wie bei den Fibonacci-Zahlen) gibt es ja hier nicht?

Und es gibt ja noch das Subset Sum Problem, was dem Rucksackproblem irgendwie ähnlich ist. Warum lässt sich das nicht als Rucksackproblem lösen?

Schonmal danke für Antworten
toad

[mehlvogel]

Ein Algorithmus zur Lösung des Rucksackproblems, als auch des Subset-Sum-Problems mit Hilfe von dynamischer Programmierung kann in der englischen Wikipedia gefunden werden:
http://en.wikipedia.org/wiki/Knapsack_problem#Dynamic_programming_solution
http://en.wikipedia.org/wiki/Subset_sum_problem#Pseudo-polynomial_time_dynamic_programming_solution
Den für das Rucksackproblem finde ich dabei allerdings deutlich besser beschrieben.

[toad]

Mein Problem bei der Lösung auf Wikipedia und auch den Lösungen die ich per google finden konnte ist, dass alles sehr kompliziert erklärt ist, gibt es vielleicht irgendwo "idiotensichere" Erklärungen der Probleme (vor allem des Rucksackproblems)

PS: Ich hab versucht die Lösung für das Rucksackproblem (ohne dynamischen Teil, den ich nicht verstanden habe) aus Wikipedia zu benutzen, aber sie funktioniert nicht wirklich, so scheint z.B das erste Element meiner Gegenstandsliste bei der Berechnung irgendwie ignoriert zu werden.


def A(i,j):
if i == 0:
return 0
if j == 0:
return 0
if cost[i] > j:
return A(i-1,j)
if cost[i] <= j:
return max(A(i-1,j), wert[i] + A(i-1,j-cost[i]))

gegenstand = ["Krone","Shirt","Tonne","Haus"]
cost = [5,1,2,20]
wert = [1000,7,80,2000]

print A(i=3,j=1000)

Das gibt als Ausgabe 2087, nicht 3087

[mehlvogel]

Das liegt daran, dass es in der mathematischen Formulierung kein Element 0 in den Kosten und Werten gibt, da die c und v Werte erst ab c_1 und v_1 definiert sind. In deiner Liste ist das aber anders, da das "0te" Elemente eben 5 bzw. 1000 ist. Füge vor diesen Werten noch irgendwas ein und es sollte funktionieren:



def A(i,j):
if i == 0:
return 0
if j == 0:
return 0
if cost[i] > j:
return A(i-1,j)
if cost[i] <= j:
return max(A(i-1,j), wert[i] + A(i-1,j-cost[i]))

gegenstand = ["Krone","Shirt","Tonne","Haus"]
cost = [0,5,1,2,20]
wert = [0,1000,7,80,2000]

print A(i=4,j=1000)


Eine schönere Methode wäre wahrscheinlich die == durch < zu ersetzen.

[toad]

cool, Danke. Mit < statt == funktioniert es. Hab jetzt noch ein dictionary ("berechnet") dazu gemacht, um schon berechnete Ergebnisse abzuspeichern.


def A(i,j):

if berechnet.has_key((i,j)):
return berechnet[(i,j)]

if i < 0:
berechnet(i,j) = 0
return 0
if j < 0:
berechnet(i,j) = 0
return 0
if cost[i] > j:
zahl = A(i-1,j)
berechnet[(i,j)] = zahl
return zahl
if cost[i] <= j:
zahl = max(A(i-1,j), wert[i] + A(i-1,j-cost[i]))
berechnet[(i,j)] = zahl
return zahl

berechnet = { }
gegenstand = ["Krone","Shirt","Tonne","Haus"]
cost = [5,1,2,20]
wert = [1000,7,80,2000]

print A(i=3,j=1000)

Allerdings frag ich mich, ob das überhaupt was bringt, denn beim Beispiel, dass ich im programm habe, kommt z.B anscheinend keine einzige Kombination von i (Anzahl der Gegenstände) und j (maximales Gewicht bzw. maximale Kosten) mehrmals vor*. Oder läuft die dynamische Programmierung hier ganz anders ab, als bei den Fibonacci-Zahlen und ich bin auf dem total falschen Weg?

*hatte zum Test einmal ganz am Anfang der Funktion print i,j geschrieben

[mehlvogel]

Könntest du deine Frage präzisieren, ich weiß nicht so ganz wodrauf du hinaus willst.

[toad]

Hallo,
wollte eigentlich fragen, ob man noch andere Sachen zwischenspeichern kann /sollte.

Bin aber inzwischen auf ein viel größeres Problem, ich wollte nun nicht nur eine Zahl sondern auch eine richtige Liste mit dem Ergebnis zurückbekommen:


if cost[i] <= j:
##max(A(i-1,j), wert[i] + A(i-1,j-cost[i]))
annahme_eins = A(i-1,j)
annahme_zwei = A(i-1,j-cost[i])
if annahme_eins > annahme_zwei:
zahl = annahme_eins
else:
ergebnis.append(gegenstand[annahme_zwei])
zahl = annahme_zwei

berechnet[i,j] = zahl
return zahl


Darufhin bekomme ich ein:


File "blaa.py", line 15
berechnet(i,j) = 0
SyntaxError: can't assign to function call

Diesselbe Fehlermeldung bekomme ich auch, wenn ich den Index für den Gegenstand und die von einer Hilfsfunktion gemeinsam als Tupel zurückgeben lasse, statt if-else zu benutzen.

[mehlvogel]

In der besagten Zeile 15 fehlen die eckigen Klammern.