In today’s xkcd comic the joke was about using the knapsack problem at a restaurant. Just for fun, I solved it in scheme.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 | (define (make-appetizer name cost) (cons name cost)) (define (name app) (car app)) (define (cost app) (cdr app)) (define delta 0.000001) (define (float-equal? x y) (< (abs (- x y)) delta)) (define appetizers (list (make-appetizer "mixed fruit" 2.15) (make-appetizer "french fries" 2.75) (make-appetizer "side salad" 3.35) (make-appetizer "hot wings" 3.55) (make-appetizer "mozzarella sticks" 4.20) (make-appetizer "sampler plate" 5.80))) (define (append-unless-null set elem) (if (null? set) '() (cons elem set))) (define (appetizers-for-cost-n apps n) (if (null? apps) '() (cond ((float-equal? (cost (car apps)) n) (list (car apps))) ((> (cost (car apps)) n) (appetizers-for-cost-n (cdr apps) n)) (else (append (map (lambda (x) (cons (car apps) x)) (appetizers-for-cost-n apps (- n (cost (car apps))))) (appetizers-for-cost-n (cdr apps) n)))))) |
Calling it with: (appetizers-for-cost-n appetizers 15.05)
Results in:
((("mixed fruit" . 2.15) ("mixed fruit" . 2.15) ("mixed fruit" . 2.15) ("mixed fruit" . 2.15) ("mixed fruit" . 2.15) ("mixed fruit" . 2.15) "mixed fruit" . 2.15) (("mixed fruit" . 2.15) ("hot wings" . 3.55) ("hot wings" . 3.55) "sampler plate" . 5.8))
