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 to pack well for the trip.

He has a good knapsack for carrying things, but knows that he can carry a maximum of only 4kg in it,   and it will have to last the whole day.

He creates a list of what he wants to bring for the trip but the total weight of all items is too much.

He then decides to add columns to his initial list detailing their weights and a numerical value representing how important the item is for the trip.



Here is the list:


 Table of potential knapsack items


 item 
 weight (dag) 
 value


 map 
 9 
 150


 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


 suntan cream 
 11 
 70


 camera 
 32 
 30


 T-shirt 
 24 
 15


 trousers 
 48 
 10


 umbrella 
 73 
 40


 waterproof trousers 
 42 
 70


 waterproof overclothes 
 43 
 75


 note-case 
 22 
 80


 sunglasses 
 7 
 20


 towel 
 18 
 12


 socks 
 4 
 50


 book 
 30 
 10


 knapsack 
 ≤400 dag 
 ?



The tourist can choose to take any combination of items from the list,
but only one of each item is available.

He may not cut or diminish the items, so he can only take whole units of any item.



Task

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

[dag = decagram = 10 grams]



Related tasks

   Knapsack problem/Bounded
   Knapsack problem/Unbounded
   Knapsack problem/Continuous
   A* search algorithm


' Knapsack problem/0-1 - 13/02/2017
dim w(22),v(22),m(22)
data=array( "map", 9, 150, "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, _
 "suntan cream", 11, 70, "camera", 32, 30 , "T-shirt", 24, 15, _
 "trousers", 48, 10, "umbrella", 73, 40, "book", 30, 10 , _
 "waterproof trousers", 42, 70, "waterproof overclothes", 43, 75 , _
 "note-case", 22, 80, "sunglasses", 7, 20, "towel", 18, 12, "socks", 4, 50)
ww=400
xw=0:iw=0:iv=0
w(1)=iw:v(1)=iv
for i1=0 to 1:m(1)=i1:j=0
 if i1=1 then
  iw=w(1)+data(j*3+1):iv=v(1)+data(j*3+2)
  if iv>xv and iw<=ww then xw=iw:xv=iv:l=m
 end if 'i1
 if iw<=ww then
  w(2)=iw: v(2)=iv
  for i2=0 to 1:m(2)=i2:j=1
   if i2=1 then
    iw=w(2)+data(j*3+1):iv=v(2)+data(j*3+2)
    if iv>xv and iw<=ww then xw=iw:xv=iv:l=m
   end if 'i2
   if iw<=ww then
    w(3)=iw: v(3)=iv
    for i3=0 to 1:m(3)=i3:j=2
     if i3=1 then
      iw=w(3)+data(j*3+1):iv=v(3)+data(j*3+2)
      if iv>xv and iw<=ww then xw=iw:xv=iv:l=m
     end if 'i3
     if iw<=ww then
      w(4)=iw: v(4)=iv
      for i4=0 to 1:m(4)=i4:j=3
       if i4=1 then
        iw=w(4)+data(j*3+1):iv=v(4)+data(j*3+2)
        if iv>xv and iw<=ww then xw=iw:xv=iv:l=m
       end if 'i4
       if iw<=ww then
        w(5)=iw: v(5)=iv
        for i5=0 to 1:m(5)=i5:j=4
         if i5=1 then
          iw=w(5)+data(j*3+1):iv=v(5)+data(j*3+2)
          if iv>xv and iw<=ww then xw=iw:xv=iv:l=m
         end if 'i5
         if iw<=ww then
          w(6)=iw: v(6)=iv
          for i6=0 to 1:m(6)=i6:j=5
           if i6=1 then
            iw=w(6)+data(j*3+1):iv=v(6)+data(j*3+2)
            if iv>xv and iw<=ww then xw=iw:xv=iv:l=m
           end if 'i6
           if iw<=ww then
            w(7)=iw: v(7)=iv
            for i7=0 to 1:m(7)=i7:j=6
             if i7=1 then
              iw=w(7)+data(j*3+1):iv=v(7)+data(j*3+2)
              if iv>xv and iw<=ww then xw=iw:xv=iv:l=m
             end if 'i7
             if iw<=ww then
              w(8)=iw: v(8)=iv
              for i8=0 to 1:m(8)=i8:j=7
               if i8=1 then
                iw=w(8)+data(j*3+1):iv=v(8)+data(j*3+2)
                if iv>xv and iw<=ww then xw=iw:xv=iv:l=m
               end if 'i8
               if iw<=ww then
                w(9)=iw: v(9)=iv
                for i9=0 to 1:m(9)=i9:j=8
                 if i9=1 then
                  iw=w(9)+data(j*3+1):iv=v(9)+data(j*3+2)
                  if iv>xv and iw<=ww then xw=iw:xv=iv:l=m
                 end if 'i9
                 if iw<=ww then
                  w(10)=iw: v(10)=iv
                  for i10=0 to 1:m(10)=i10:j=9
                   if i10=1 then
                    iw=w(10)+data(j*3+1):iv=v(10)+data(j*3+2)
                    if iv>xv and iw<=ww then xw=iw:xv=iv:l=m
                   end if 'i10
                   if iw<=ww then
                    w(11)=iw: v(11)=iv
                    for i11=0 to 1:m(11)=i11:j=10
                     if i11=1 then
                      iw=w(11)+data(j*3+1):iv=v(11)+data(j*3+2)
                      if iv>xv and iw<=ww then xw=iw:xv=iv:l=m
                     end if 'i11
                     if iw<=ww then
                      w(12)=iw: v(12)=iv
                      for i12=0 to 1:m(12)=i12:j=11
                       if i12=1 then
                        iw=w(12)+data(j*3+1):iv=v(12)+data(j*3+2)
                        if iv>xv and iw<=ww then xw=iw:xv=iv:l=m
                       end if 'i12
                       if iw<=ww then
                        w(13)=iw: v(13)=iv
                        for i13=0 to 1:m(13)=i13:j=12
                         if i13=1 then
                          iw=w(13)+data(j*3+1):iv=v(13)+data(j*3+2)
                          if iv>xv and iw<=ww then xw=iw:xv=iv:l=m
                         end if 'i13
                         if iw<=ww then
                          w(14)=iw: v(14)=iv
                          for i14=0 to 1:m(14)=i14:j=13
                           if i14=1 then
                            iw=w(14)+data(j*3+1):iv=v(14)+data(j*3+2)
                            if iv>xv and iw<=ww then xw=iw:xv=iv:l=m
                           end if 'i14
                           if iw<=ww then
                            w(15)=iw: v(15)=iv
                            for i15=0 to 1:m(15)=i15:j=14
                             if i15=1 then
                              iw=w(15)+data(j*3+1):iv=v(15)+data(j*3+2)
                              if iv>xv and iw<=ww then xw=iw:xv=iv:l=m
                             end if 'i15
                             if iw<=ww then
                              w(16)=iw: v(16)=iv
                              for i16=0 to 1:m(16)=i16:j=15
                               if i16=1 then
                                iw=w(16)+data(j*3+1):iv=v(16)+data(j*3+2)
                                if iv>xv and iw<=ww then xw=iw:xv=iv:l=m
                               end if 'i16
                               if iw<=ww then
                                w(17)=iw: v(17)=iv
                                for i17=0 to 1:m(17)=i17:j=16
                                 if i17=1 then
                                  iw=w(17)+data(j*3+1):iv=v(17)+data(j*3+2)
                                  if iv>xv and iw<=ww then xw=iw:xv=iv:l=m
                                 end if 'i17
                                 if iw<=ww then
                                  w(18)=iw: v(18)=iv
                                  for i18=0 to 1:m(18)=i18:j=17
                                   if i18=1 then
                                    iw=w(18)+data(j*3+1):iv=v(18)+data(j*3+2)
                                    if iv>xv and iw<=ww then xw=iw:xv=iv:l=m
                                   end if 'i18
                                   if iw<=ww then
                                    w(19)=iw: v(19)=iv
                                    for i19=0 to 1:m(19)=i19:j=18
                                     if i19=1 then
                                      iw=w(19)+data(j*3+1):iv=v(19)+data(j*3+2)
                                      if iv>xv and iw<=ww then xw=iw:xv=iv:l=m
                                     end if 'i19
                                     if iw<=ww then
                                      w(20)=iw: v(20)=iv
                                      for i20=0 to 1:m(20)=i20:j=19
                                       if i20=1 then
                                        iw=w(20)+data(j*3+1):iv=v(20)+data(j*3+2)
                                        if iv>xv and iw<=ww then xw=iw:xv=iv:l=m
                                       end if 'i20
                                       if iw<=ww then
                                        w(21)=iw: v(21)=iv
                                        for i21=0 to 1:m(21)=i21:j=20
                                         if i21=1 then
                                          iw=w(21)+data(j*3+1):iv=v(21)+data(j*3+2)
                                          if iv>xv and iw<=ww then xw=iw:xv=iv:l=m
                                         end if 'i21
                                         if iw<=ww then
                                          w(22)=iw: v(22)=iv
                                          for i22=0 to 1:m(22)=i22:j=21
                                           nn=nn+1
                                           if i22=1 then
                                            iw=w(22)+data(j*3+1):iv=v(22)+data(j*3+2)
                                            if iv>xv and iw<=ww then xw=iw:xv=iv:l=m
                                           end if 'i22
                                           if iw<=ww then
                                           end if 'i22
                                          next:m(22)=0
                                         end if 'i21
                                        next:m(21)=0
                                       end if 'i20
                                      next:m(20)=0
                                     end if 'i19
                                    next:m(19)=0
                                   end if 'i18
                                  next:m(18)=0
                                 end if 'i17
                                next:m(17)=0
                               end if 'i16
                              next:m(16)=0
                             end if 'i15
                            next:m(15)=0
                           end if 'i14
                          next:m(14)=0
                         end if 'i13
                        next:m(13)=0
                       end if 'i12
                      next:m(12)=0
                     end if 'i11
                    next:m(11)=0
                   end if 'i10
                  next:m(10)=0
                 end if 'i9
                next:m(9)=0
               end if 'i8
              next:m(8)=0
             end if 'i7
            next:m(7)=0
           end if 'i6
          next:m(6)=0
         end if 'i5
        next:m(5)=0
       end if 'i4
      next:m(4)=0
     end if 'i3
    next:m(3)=0
   end if 'i2
  next:m(2)=0
 end if 'i1
next:m(1)=0
for i=1 to 22
 if l(i)=1 then wlist=wlist&vbCrlf&data((i-1)*3)
next
Msgbox mid(wlist,3)&vbCrlf&vbCrlf&"weight="&xw&vbCrlf&"value="&xv,,"Knapsack - nn="&nn