cool, Danke. Mit < statt == funktioniert es. Hab jetzt noch ein dictionary ("berechnet") dazu gemacht, um schon berechnete Ergebnisse abzuspeichern.
Code:
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
Lesezeichen