Following is my solution to Knapsack problem using all combinations of the sent list of items (in Racket programming language). Although it is very short, I am sure it can be improved in many ways.
(define (maxI L) (- (length L) (length (member (apply max L) L))))
(define (knapsack maxwt itemL)
(let* ((combL (filter (λ (x) (<= (apply + (map second x)) maxwt))
(combinations itemL)))
(totalvalueL (map (λ (x) (apply + (map third x))) combL))
(maxvalindex (maxI totalvalueL)))
(list-ref combL maxvalindex)))
Following is code with comments to explain different steps:
; support fn to find index of largest number in a list:
(define (maxI L) (- (length L) (length (member (apply max L) L))))
; Main fn - only 4 statements:
(define (knapsack maxwt itemL)
(let* ((combL (filter (λ (x) (<= (apply + (map second x)) maxwt)) ; Get all combinations and filter out
(combinations itemL))) ; those where total wt is upto maxwt;
; Other filters can be added here, e.g. if both wt and volume are limiting;
(totalvalueL (map (λ (x) (apply + (map third x))) combL)) ; Get total values in each combination;
(maxvalindex (maxI totalvalueL))) ; Find index of maximum value;
;(printf "Total value = ~a~n" (list-ref totalvalueL maxvalindex)) ; uncomment to print total value;
;(printf "Total wt = ~a~n" (apply + (map second (list-ref combL maxvalindex)))) ; uncomment to print total wt;
(list-ref combL maxvalindex))) ; return combination at this index;
Usage:
(define Itemslist '((a 20 100) ; (name wt value) ;
(b 10 20)
(c 30 130)))
(define MaxWtAllowed 30)
(knapsack MaxWtAllowed Itemslist)
Output:
Total value = 130
Total wt = 30
'((c 30 130))
Another test:
(set! Itemslist '((a 3 50) ; (name wt value) ;
(b 6 30)
(c 4 40)
(d 5 10)))
(set! MaxWtAllowed 10)
(knapsack MaxWtAllowed Itemslist)
Output:
Total value = 90
Total wt = 7
'((a 3 50) (c 4 40))
I find that it gets stuck with large lists (as one used on https://rosettacode.org/wiki/Knapsack_problem/0-1#Racket - see its example run).
(knapsack 400
'((map 9 150) ; 9 is weight, 150 is value
(compass 13 35) (water 153 200) (sandwich 50 160)
(glucose 15 60) (tin 68 45)(banana 27 60) (apple 39 40)
(cheese 23 30) (beer 52 10) (cream 11 70) (camera 32 30)
(T-shirt 24 15) (trousers 48 10) (umbrella 73 40)
(trousers 42 70) (overclothes 43 75) (notecase 22 80)
(glasses 7 20) (towel 18 12) (socks 4 50) (book 30 10)))
I get "Interaction disabled"
message most of the time (on DrRacket IDE). Sometimes it runs and then it give correct answer (same as on rosettacode page):
Total value = 1030
Total wt = 396
'((map 9 150)
(compass 13 35)
(water 153 200)
(sandwich 50 160)
(glucose 15 60)
(banana 27 60)
(cream 11 70)
(trousers 42 70)
(overclothes 43 75)
(notecase 22 80)
(glasses 7 20)
(socks 4 50))
Any suggestions will be appreciated.
get-indexes
instead ofgetIndexes
. \$\endgroup\$