wir haben von der Uni eine aufgabe bekommen. Es geht um Das Knapsack Problem und wir sollen es mittel backtracking lösen. Dazu haben wir ein Skript in natürlicher Sprache bekommen:
Backtracking(aktuelle Auswahl):
Berechne Gewicht und Wert der aktuellen Auswahl.
Falls das zulässige Gesamtgewicht überschritten wurde:
Gib eine leere Liste zurück.
Sonst:
Setze die aktuelle Auswahl als bisher beste.
Wiederhole für jedes Objekt, das in der aktuellen Auswahl noch nicht vorkommt:
Füge das Objekt zur aktuellen Auswahl hinzu und rufe die Funktion rekursiv für diese Auswahl auf.
Falls diese Suche ein besseres Ergebnis liefert als die bisher beste Auswahl:
Speichere die zurückgelieferte Auswahl als bisher beste.
Entferne das Objekt anschließend wieder aus der aktuellen Auswahl.
Gib die so ermittelte beste Auswahl zurück.
Code: Alles auswählen
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)
max_gewicht = 320
def berechne_gewicht(auswahl):
gesamtgewicht = 0
for i in auswahl:
gesamtgewicht = gesamtgewicht + gewichte[i]
return gesamtgewicht
def berechne_wert(auswahl):
gesamtwert = 0
for i in auswahl:
gesamtwert = gesamtwert + werte[i]
return gesamtwert
def fehlende_objekte(auswahl):
gefunden = []
for i in range(0, anzahl):
gefunden = gefunden + [False]
for i in auswahl:
gefunden[i] = True
nummern = []
for i in range(0, anzahl):
if not gefunden[i]:
nummern = nummern + [i]
return nummern
def finde_auswahl(akt_auswahl):
gewicht = berechne_gewicht(akt_auswahl)
wert = berechne_wert(akt_auswahl)
if gewicht > max_gewicht:
return []
else:
beste_auswahl = akt_auswahl
for i in fehlende_objekte(akt_auswahl):
akt_auswahl = akt_auswahl + [i]
rekursiv = finde_auswahl(akt_auswahl)
if berechne_wert(rekursiv) > wert:
beste_auswahl = rekursiv
akt_auswahl.remove(i)
return beste_auswahl
result = finde_auswahl([0,1,2,3])
print(result)
als ergebnis sollte eigentlich die liste [0,1,2,4] bei herauskommen. allerdings klapps bei mir nicht. hab schon den ganzen tag versucht die fehler zu finden, aber ohne erfolg. hoffe mir kann hier irgendjemand weiterhelfen