How to resolve the algorithm Knapsack problem/Bounded step by step in the J programming language

Published on 12 May 2024 09:40 PM
#J

How to resolve the algorithm Knapsack problem/Bounded step by step in the J programming language

Table of Contents

Problem Statement

A tourist wants to make a good trip at the weekend with his friends. They will go to the mountains to see the wonders of nature.   So he needs some items during the trip.   Food, clothing, etc.   He has a good knapsack for carrying the things, but he knows that he can carry only 4 kg weight in his knapsack, because they will make the trip from morning to evening. He creates a list of what he wants to bring for the trip, but the total weight of all items is too much.   He adds a value to each item.   The value represents how important the thing for the tourist. The list contains which items are the wanted things for the trip, what is the weight and value of an item, and how many units does he have from each items.

This is the list:

The tourist can choose to take any combination of items from the list, and some number of each item is available   (see the column   piece(s)   in the list above). He may not cut the items, so he can only take whole units of any item.

Show which items does the tourist carry in his knapsack so that their total weight does not exceed 4 kg, and their total value is maximized.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Knapsack problem/Bounded step by step in the J programming language

Source code in the j programming language

'names numbers'=:|:".;._2]0 :0
  'map';                      9       150        1
  'compass';                 13        35        1
  'water';                  153       200        2
  'sandwich';                50        60        2
  'glucose';                 15        60        2
  'tin';                     68        45        3
  'banana';                  27        60        3
  'apple';                   39        40        3
  'cheese';                  23        30        1
  'beer';                    52        10        3
  'suntan cream';            11        70        1
  'camera';                  32        30        1
  'T-shirt';                 24        15        2
  'trousers';                48        10        2
  'umbrella';                73        40        1
  'waterproof trousers';     42        70        1
  'waterproof overclothes';  43        75        1
  'note-case';               22        80        1
  'sunglasses';               7        20        1
  'towel';                   18        12        2
  'socks';                    4        50        1
  'book';                    30        10        2
)

'weights values pieces'=:|:numbers
decode=: (pieces+1)&#:

pickBest=:4 :0
  NB. given a list of options, return the best option(s)
  n=. decode y
  weight=. n+/ .*weights
  value=.  (x >: weight) * n+/ .*values
  (value = >./value)#y
)

bestCombo=:3 :0
   limit=. */pieces+1
   i=. 0
   step=. 1e6
   best=. ''
   while.i<limit do.
      best=. 400 pickBest best,(#~ limit&>)i+i.step
      i=. i+step
   end.
   best
)

   bestCombo''
978832641


   decode 978832641
1 1 1 0 2 0 3 0 1 0 1 0 0 0 0 0 1 1 1 0 1 0
    (0<decode 978832641) # (":,.decode 978832641),.' ',.names
1 map                   
1 compass               
1 water                 
2 glucose               
3 banana                
1 cheese                
1 suntan cream          
1 waterproof overclothes
1 note-case             
1 sunglasses            
1 socks                 
   weights +/ .* decode 978832641
396
   values +/ .* decode 978832641
1010


dyn=:3 :0
  m=. 0$~1+400,+/pieces NB. maximum value cache
  b=. m                 NB. best choice cache
  opts=.+/\0,pieces     NB. distinct item counts before each piece
  P=. */\1+0,pieces   NB. distinct possibilities before each piece
  for_w.1+i.400 do.
    for_j.i.#pieces do.
      n=. i.1+j{pieces         NB. possible counts for this piece
      W=. n*j{weights          NB. how much they weigh
      s=. w>:W                 NB. permissible options
      v=. s*n*j{values         NB. consequent values
      base=. j{opts            NB. base index for these options
      I=. <"1 w,.n+base        NB. consequent indices
      i0=. <w,base             NB. status quo index
      iN=. <"1 (w-s*W),.base   NB. predecessor indices
      M=. >./\(m{~i0)>.v+m{~iN NB. consequent maximum values
      C=. (n*j{P)+b{~iN        NB. unique encoding for each option
      B=. >./\(b{~i0)>. C * 2 ~:/\ 0,M NB. best options, so far
      m=. M I} m       NB. update with newly computed maxima
      b=. B I} b       NB. same for best choice
    end.
  end.
  |.(1+|.pieces)#:{:{:b
)

   dyn''
1 1 1 0 2 0 3 0 1 0 1 0 0 0 0 0 1 1 1 0 1 0

You may also check:How to resolve the algorithm Amicable pairs step by step in the Rust programming language
You may also check:How to resolve the algorithm Greedy algorithm for Egyptian fractions step by step in the Common Lisp programming language
You may also check:How to resolve the algorithm Balanced brackets step by step in the zkl programming language
You may also check:How to resolve the algorithm Luhn test of credit card numbers step by step in the bc programming language
You may also check:How to resolve the algorithm Abundant odd numbers step by step in the JavaScript programming language