(define (Rucksack-packen Gewicht Teilgewichte Ergebnis) (cond ((zero? Gewicht) ; Lösung gefunden ! Ergebnis) ((null? Teilgewichte) ; nicht lösbar #f) ((< Gewicht (car Teilgewichte)) ; erster geht nicht (Rucksack-packen Gewicht (cdr Teilgewichte) Ergebnis)) (else ; einpacken und weiter (Rucksack-packen (- Gewicht (car Teilgewichte)) (cdr Teilgewichte) (cons (car Teilgewichte) Ergebnis)))))
Mit cond beginnt eine Mehrfachverzweigung.
Da das Gewicht bei der Rekursion abgebaut wird, ist eines der Abbruchkriterien bei der Rekursion, dass das Gewicht den Wert 0 erreicht hat. [Achtung: zero? ist das Prädikat, nicht null?] Dann hat die bisher gefundene Kombination on Gewichten genau gepasst.
Wenn die Liste der möglichen Teilgewichte, die bei der Rekursion abgebaut wird, leer ist, hat man keine Alternativen mehr. Da vorher überprüft wurde, ob das letzte Gewicht so gepasst hatte, dass s genau aufging, weiß man nun, dass es keine Lösung für das Problem gab. Das Prädikat für eine leere Liste ist null? im Sinne von "nichts". Als Wert der Funktion wird falsch (#f) zurückgegeben.
Ist das aktuelle Restgewicht kleiner als das erste Element der Liste (car) der Teilgewichte, dann passt dieses nicht mehr in den Rucksack. Es muss beseite gelegt werden.
Für unseren nächsten Rekursionsschritt ist daher die Restliste (cdr) der aktuellen Liste zu verwenden.
Anderenfalls ( else ) passt unser erstes Teilgewicht und wird in den Rcksack gepackt.
cons fügt einer Liste ein neues erstes Element hinzu.
Beachten Sie bei allen beschriebenen Befehlen das funktionale Denken, z.B. cons:
cons ist eine Funktion, die zwei Parameter braucht, von denen der zweite eine Liste sein muss. Ihr Wert ist eine neue Liste. Diese neue Liste enthält an der ersten Stelle den ersten cons übergebenen Parameter und als Restliste die an zweiter Stelle übergebene Liste.
Wenn Sie diese Funktion prozedural verwenden, wird der Wert zwar bestimmt, anschließend aber sofort wieder vergessen. Hier wird er dagegen der nächsten Auswertungsstufe als Parameter übergeben und kann daher weiter verwendet werden.