Satisfizierung Ablauf

Rucksack packen "gierig" versucht


2. Fall: möglichst viel - Optimierungsproblem

(define
  (Rucksack-packen Gewicht Teilgewichte Ergebnis)
  (cond
    ((zero? Gewicht)          ; Lösung gefunden !
     Ergebnis)
    ((null? Teilgewichte)     ; nicht voll erfüllt
     (cons "nicht exakt" Ergebnis))
    ((< 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)))))

Wird die Funktion nun z.B. mit

(Rucksack-packen 101 '(30 30 30 20 20 20 15 15 5 3 2 1 1)) ())

aufgerufen gibt sie als Wert die Liste

(1 2 3 5 30 30 30)

aus.

Will man den Ablauf verfolgen, setzt man unmittelbar vor dem cond den folgenden Aufruf ein:

     (bkpt Gewicht Teilgewichte Ergebnis)

zurück