EntwurfRZ

Aus ProgrammingWiki

Archivierte Version vom 2016-01-21T20:09:04+00:00. Aktuelle Version

(define gegenstaende
  (list->vector
   '("dummy"
     (2 . 6)
     (2 . 3)
     (6 . 5)
     (5 . 4)
     (4 . 6))))

(define gewicht
  (lambda(i)
    (car (vector-ref gegenstaende i))))

(define wert
  (lambda(i)
    (cdr (vector-ref gegenstaende i))))

(define gesamtwert-rekursiv-memo
  (let ((memoliste '())) 
    (lambda (n k)
      (let ((rek-aufrufe 0))
	(letrec
	    ((gesamtwert-memo  
	      (lambda (i g)
		(let ((memowert (assoc (cons i g) memoliste)))
		  (if memowert
		      (cdr memowert)
		      (let ((resultat (gesamtwert i g)))
			(set! memoliste
                              (cons (cons (cons i g) resultat) memoliste))
			resultat)))))
	     (gesamtwert
	      (lambda (i g)
		(set! rek-aufrufe (+ rek-aufrufe 1)) 
		(cond
                  ((= i 0) 0)
		  ((> (gewicht i) g) (gesamtwert-memo (- i 1) g)) 
		  (else
                   (max
                    (gesamtwert-memo (- i 1) g) 
                    (+ (gesamtwert-memo (- i 1) (- g (gewicht i)))(wert i))))))))
	  (list (gesamtwert n k) rek-aufrufe (length memoliste)))))))

(gesamtwert-rekursiv-memo 5 10)

EntwurfRZ

Suche