Gesamtwert-rekursiv-memo Codes3frehrl2016

Aus ProgrammingWiki

(define gegenstaende
  (list->vector
   '("dummy"
     (13 . 19)
     (11 . 20)
     (17 . 23)
     (15 . 21)
     (16 . 27)
     (14 . 25)
     (18 . 25)
     (10 . 18)
     (19 . 24)
     (12 . 17))))
     
     
;Liste wird auf Vektor abgebildet, hier von 0 bis 10, um die Nummerierung mit 1 zu starten, wird 0 nicht benutzt(dummy). 

(define gewicht
  (lambda(i)
    (car (vector-ref gegenstaende i))))
;um auf das Gewicht zuzugreifen, wird auf das erste Element aus dem Vektor an der Position i zugegriffen.

(define wert
  (lambda(i)
    (cdr (vector-ref gegenstaende i))))
;um auf den Wert zuzugreifen, wird auf das erste Element aus dem Vektor an der Position i zugegriffen.

(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 10 120);

Gesamtwert-rekursiv-memo Codes3frehrl2016

Suche