Das deutsche Python-Forum

Hi,
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

das knapsack problem: man hat einen rucksack, der nur ein bestimmtes gewicht aushält(max_gewicht) und man hat items mit einem bestimmtem gewicht und einem bestimmtem wert. nun will man wissen, durch welche kombination man die höchsten werte hat, ohne das diese kombination das max. gewicht überschreitet

Eventuell hilft dir dieses Video. https://www.youtube.com/watch?v=xOlhR_2QCXY

Gewichte und Werte sind bei Dir Konstanten. Damit man sie als solche erkennt, werden sie nach Konvention komplett gross geschrieben:

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` ist unnötig, da sie ja jederzeit aus GEWICHTE oder WERTE ermittelt werden kann.
`MAX_GEWICHT` scheint auch eine Konstante zu sein, obwohl das wirklich besser ein Argument von `finde_auswahl` sein sollte.

Für `berechne_gewicht` ist die `sum`-Funktion ganz hilfreich:

Code: Alles auswählen

def berechne_gewicht(auswahl):
    return sum(GEWICHTE[i] for i in auswahl)

def berechne_wert(auswahl):
    return sum(WERTE[i] for i in auswahl)

In `fehlende_objekte` (die Funktion sollte eigentlich auch nach einer Tätigkeit benannt werden) erzeugst Du erst eine Liste mit False, die danach verändert wird. Das geht einfacher mit [False] * anzahl. Um ein Element an eine Liste anzuhängen, gibt es append, statt erst eine Einelementige Liste zu erzeugen und dann daraus eine Kopie der ursprünglichen Liste zu erzeugen und diese mit der einelementigen Liste zu verbinden.

Code: Alles auswählen

def fehlende_objekte(auswahl):
    gefunden = [False] * len(GEWICHTE)
    for i in auswahl:
        gefunden[i] = True
    nummern = []
    for i in range(0, len(GEWICHTE)):
        if not gefunden[i]:
            nummern.append(i)
    return nummern

Einfacher geht es, indem Du direkt schaust, ob i in der Auswahl ist, oder nicht:

Code: Alles auswählen

def fehlende_objekte(auswahl):
    return [i for i in range(0, len(GEWICHTE))
        if i not in auswahl]

In `finde_auswahl` wird es dann kompliziert. Du mischst Zeilen, in denen Du mit der selben Liste arbeitest und Zeilen, in denen Du Kopien machst, so dass es schwer zu ermitteln ist, welche Liste den bei dem remove mit verändert wird. `akt_auswahl` und `beste_auswahl` können die selbe Liste sein. Dass nur bei einem besseren Ergebnis i wieder entfernt wird, dürfte auch ein Fehler sein. Das alles ließe sich einfach vermeiden, indem Du nie `remove` aufrufst, sondern finde_auswahl(akt_auswahl + ) benutzt.
Du hast zwar eine beste_auswahl, aber keinen besten_wert.

Das deutsche Python-Forum

komme bei aufgabe nicht weiter

komme bei aufgabe nicht weiter

Re: komme bei aufgabe nicht weiter

Re: komme bei aufgabe nicht weiter

Re: komme bei aufgabe nicht weiter