0 - 1 KnapSack Problem | Problem mit Funktion

[Stryker]

Hallo, ich habe von der Uni eine Aufgabe zu dem 1-0 KnapSack Problem gestellt bekommen, zu welchem es hier im Forum schon einen Beitrag gibt. Ich bin nun einen anderen Ansatz gegangen und habe folgende Funktion definiert:

GEWICHTE = [50, 50, 60, 80, 100, 110, 120, 150, 150, 200]
WERTE = [80, 80, 60, 50, 100, 90, 100, 170, 200, 240]
anzahl = len(gewichte)

def finde_max(max_gewicht, gewichte, werte, anzahl):
if anzahl == 0:
return 0

if gewichte[anzahl-1] > max_gewicht:
return finde_max(max_gewicht, gewichte, werte, anzahl-1)

else:
return max(werte[anzahl-1] + finde_max(max_gewicht-gewichte[anzahl-1], gewichte, werte, anzahl-1),
finde_max(max_gewicht, gewichte, werte, anzahl-1))

Wir haben aber leider ein recht starres Programmgerüst bekommen, das mit einer Liste weiterarbeitet, welche die Indizes der Elemente enthält, die benutz wurden. Ich habe nun schon länger versucht mir auch eben diese Liste ausgeben zu lassen, bin daran aber ziemlich kläglich gescheitert. Ist dies ohne weiteres möglich zu implementieren, oder muss ich die Funktion grundlegend ändern dafür?

Vielen Dank schon mal für Hilfe und Lieben Gruß

[Sirius3]

Hier ist ein Kollege mit der selben Aufgabe: viewtopic.php?f=1&t=47461

`gewichte` ist nicht definiert so dass es bei `anzahl` einen NameError gibt. Im anderen Thread habe ich schon geschrieben, dass man überhaupt keine Anzahl speichern sollte, da man sie über die Länge der Liste direkt bekommt.
Beim Aufruf von finde_max sind max_gewicht, gewichte und werte nicht definiert.
Kannst Du mal beschreiben, wie Dein Algorithmus funktionieren soll?

[Stryker]

Zu Anzahl: Das ist ist so im Code vorgegeben, daher habe ich das so weiter genutzt. Das man das auch per len(gewichte) direkt in der Funktion bekommt geht natürlich, aber Profs bzw die Prüfer sind recht penibel was sowas angeht, daher ist man meistens auf der sicheren Seite, wenn man das beibehält.

Zur Funktionsweise des Algorithmus: Ich habe diesen Code tatsächlich einfach aus dem Netz. Er bringt mir so eh noch nichts, da wir die Liste mit der optimalen Auswahl benötigen. Daher war meine Frage, ob dies überhaupt möglich ist.

[DeaD_EyE]

Und hier nochmal auf Englisch: https://python-forum.io/Thread-0-1-KnapSack-problem