;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;
; The knapsack problem and a (naive) algorithm for it
; Algorithm is based on branch and bound, and can be made better by
; (a) using a lower boun, ie. do not explore a solution
;     that cannot possibly be better than the best so far
; (b) Try and make good initial choices, leading to better lower
;     bound during search
;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(define *trace* #t)
(define *best-cost* 0)
(define *best-soln* nil)
(define *best-weight* 0)

(define (rcons e l)
  (append l (list e)))

(define (0-1-knapsack weights values capacity)
  (cond (*trace* (print (list '0-1-knapsack weights values capacity))))
  (let ((best-soln '())
	(best-weight 0)
	(best-value 0)
	(n (vector-length values))
	(calls 0))

    (define (knapsack i cweight cvalue csoln)
      (cond (*trace* (print (list 'knapsack i cweight cvalue csoln))))
      (set! calls (+ 1 calls))
      (cond ((and (<= cweight capacity) (> cvalue best-value))
	     (set! best-soln csoln)
	     (set! *best-soln* csoln)
	     (set! best-weight cweight)
	     (set! *best-weight* cweight)
	     (set! best-value cvalue)
	     (set! *best-cost* cvalue)))
      (cond ((and (< i n) (< cweight capacity))
	     (knapsack (+ i 1)
		       (+ cweight (vector-ref weights i))
		       (+ cvalue (vector-ref values i))
		       (rcons 1 csoln))
	     (knapsack (+ i 1) cweight cvalue (rcons 0 csoln)))))

    (knapsack 0 0 0 '())
    (list best-weight best-value best-soln calls)))
;;;
;;; Given a vector of weights, a vector of values, and a capacity 
;;; constraint, find a selection of items such that the sum of their
;;; weights is less than or equal to the capacity constraints, and the 
;;; sum of their values is a maximum
;;;

;;;
;;; Demo's below
;;;

(define z (list->vector '(7 5 4 4 1)))
(0-1-knapsack z z 10) ; see AHU page 66
(print "
**********************************************")
(define weights (list->vector '(3 8 6 4 2)))
(define values (list->vector '(2 12 9 3 5)))
(0-1-knapsack weights values 9) ; see Wilson and Watkins page 205
(print "
**********************************************")
(set! *trace* #f)