背包问题-动态规划scheme实现

;动态规划问题适用于：

;1、最优子问题 一个问题总是可以分成两个或多个子问题的最优解来解决，如背包问题中当前问题的最

;优解可以通过1-不包含当前物品时的最优解，2-包含当前物品时的最优解两个子问题来解决

;2、重叠子问题

;子问题计算过程中存在重复计算部分

;动态规划问题的本质：用空间换取时间

#lang scheme

(define memq '())

(define callcount 0)

(define (exist queue i aw)

    (if (null? queue)

        #f

        (if (and (= (caar queue) i) (= (cadar queue) aw))

            #t

            (exist (cdr queue) i aw))))

(define (getmemq  queue i aw)

        (if (and (= (caar queue) i) (= (cadar queue) aw))

            (caddar queue)

            (getmemq (cdr queue) i aw)))

(define (insertmemq i aw v)

  (set! memq (append memq (list (list i aw v)))))

(define weight '(30 31 70 40 50 20 35 23 45 27 85 5  10 15 1 2 4 8 7 9 11 43 50 95 78 80 65 30 31 70 40 50 20 35 23))

;(define weight '(30 31 70 40 50 20 35 23 45 27 85 5  10 ))

(define value  '(50 50 90 50 70 40 53 30 55 35 90 15 30 41 2 4 8 16 15 17 20 60 99 180 160 170 140 50 50 90 50 70 40 53 30))

;(define value  '(50 50 90 50 70 40 53 30 55 35 90 15 30))

  

(define (getvalue-1 l i)

  (list-ref l i))

(define (max a b)

  (if (> a b)

      a

      b))

(define (newbest w v i aw)

  (set! callcount (+ 1 callcount))

  (if (exist memq i aw)

      (getmemq memq i aw)

      (if (= i 0)

          (if (<= (getvalue-1 w i) aw)

              (begin 

                (insertmemq i aw (getvalue-1 v i))

                (getvalue-1 v i))

              (begin 

                (insertmemq i aw 0)

                0))

          (let ((without_i 0)

                (with_i 0))

            (set! without_i (newbest w v (- i 1) aw))

            (if (> (getvalue-1 w i) aw)

                without_i

                (set! with_i (+ (getvalue-1 v i) (newbest w v (- i 1) (- aw (getvalue-1 w i))))))

            (insertmemq i aw (max without_i with_i))

            (max without_i with_i)))))

(newbest weight value (- (length weight) 1) 100)

callcount