3
\$\begingroup\$

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.

\$\endgroup\$
4
  • 1
    \$\begingroup\$ Didn't you ask that a few hours ago? A probably better approach to get more attention, is to edit your question with any improvement you can think of. \$\endgroup\$ Mar 18, 2017 at 13:24
  • 1
    \$\begingroup\$ I was using value/weight ratio approach but I realized that does not work in many sets. So I had deleted that question. For example, for (value wt) items of ((100 20)(20 10)(130 30)) with max wt of 30- I was getting ((100 20)(20 10)) with that approach (since (100 20) has the best value/wt ratio) while correct answer is ((130 30)). \$\endgroup\$
    – rnso
    Mar 18, 2017 at 13:41
  • 1
    \$\begingroup\$ Camel case isn't used in Racket. Useget-indexes instead of getIndexes. \$\endgroup\$
    – soegaard
    Mar 18, 2017 at 20:28
  • \$\begingroup\$ Since camel case is used at many places here, I am not changing it at present. I will keep this in mind in future. \$\endgroup\$
    – rnso
    Mar 19, 2017 at 2:29

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.