Knapsack Problem/0-1 - Rosetta Code

[B+]

reference: rosettacode.org/wiki/Knapsack_problem/0-1

You know I thought this was going to be one of those deals where you have to try all the combinations of items and weights and optimize values but no a simple sort as you load the array with data was all it needed. Easy as eating pie. ;-))


JB solution:

' "Knapsack problem/0-1 - Rosetta Code" 'b+ 2020-10-04 trans
' w < 400   http://rosettacode.org/wiki/Knapsack_problem/0-1
DIM t$(22)
FOR i = 1 TO 22
   READ dat$
   CALL loadSort dat$
NEXT
' The problem is solved now it's just a matter of printing out the solution:
PRINT "      *** Knapsack Items Sorted by Value Per Unit Weight ***"
PRINT " #: Item:         Wght:  Val:   V/W:  Accum W:    Packed or Not: Value Packed:"
FOR i = 1 TO 22
   PRINT RIGHT$(SPACE$(3) + STR$(i), 3); SPACE$(1);
   PRINT LEFT$(word$(t$(i), 1, ",") + SPACE$(15), 15);
   PRINT RIGHT$(SPACE$(4) + WORD$(t$(i), 2, ","), 4);
   PRINT RIGHT$(SPACE$(6) + WORD$(t$(i), 3, ","), 6);
   PRINT RIGHT$(SPACE$(7) + STR$(INT(100 * VAL(WORD$(t$(i), 3, ",")) / VAL(WORD$(t$(i), 2, ",")))/100), 7);
   totW = totW + VAL(WORD$(t$(i), 2, ","))
   PRINT RIGHT$(SPACE$(10) + STR$(totW), 10); SPACE$(4);
   IF totW < 400 THEN
       PRINT "Packed!";
       totV = totV + VAL(WORD$(t$(i), 3, ","))
       PRINT RIGHT$(SPACE$(21) + STR$(totV), 21)
   ELSE
       PRINT "Not included."
   END IF
NEXT

DATA "map,9,150"
DATA "compass,13,35"
DATA "water,153,200"
DATA "sandwich,50,160"
DATA "glucose,15,60"
DATA "tin,68,45"
DATA "banana,27,60"
DATA "apple,39,40"
DATA "cheese,23,30"
DATA "beer,52,10"
DATA "suntan cream,11,70"
DATA "camera,32,30"
DATA "T-shirt,24,15"
DATA "trousers,48,10"
DATA "umbrella,73,40"
DATA "WP_trousers,42,70"
DATA "WP_wear,43,75"
DATA "note-case,22,80"
DATA "sunglasses,7,20"
DATA "towel,18,12"
DATA "socks,4,50"
DATA "book,30,10"

SUB loadSort insert$
   t$(0) = str$(val(t$(0)) + 1) 'track the upper bound in t$(0)
   ub = val(t$(0))
   IF ub > 1 THEN
       FOR j = 1 TO ub - 1
           IF val(word$(insert$, 3, ",")) / val(word$(insert$, 2, ","))  > val(word$(t$(j), 3, ","))/ val(word$(t$(j), 2, ",")) THEN
               FOR k = ub TO j + 1 STEP -1
                   t$(k) = t$(k - 1)
               NEXT
               EXIT FOR
           END IF
       NEXT
       t$(j) = insert$
   ELSE
       t$(1) = insert$
   END IF
END SUB


Output:
     *** Knapsack Items Sorted by Value Per Unit Weight ***
#: Item:         Wght:  Val:   V/W:  Accum W:    Packed or Not: Value Packed:
 1 map               9   150  16.66         9    Packed!                  150
 2 socks             4    50   12.5        13    Packed!                  200
 3 suntan cream     11    70   6.36        24    Packed!                  270
 4 glucose          15    60      4        39    Packed!                  330
 5 note-case        22    80   3.63        61    Packed!                  410
 6 sandwich         50   160    3.2       111    Packed!                  570
 7 sunglasses        7    20   2.85       118    Packed!                  590
 8 compass          13    35   2.69       131    Packed!                  625
 9 banana           27    60   2.22       158    Packed!                  685
10 WP_wear          43    75   1.74       201    Packed!                  760
11 WP_trousers      42    70   1.66       243    Packed!                  830
12 water           153   200    1.3       396    Packed!                 1030
13 cheese           23    30    1.3       419    Not included.
14 apple            39    40   1.02       458    Not included.
15 camera           32    30   0.93       490    Not included.
16 towel            18    12   0.66       508    Not included.
17 tin              68    45   0.66       576    Not included.
18 T-shirt          24    15   0.62       600    Not included.
19 umbrella         73    40   0.54       673    Not included.
20 book             30    10   0.33       703    Not included.
21 trousers         48    10    0.2       751    Not included.
22 beer             52    10   0.19       803    Not included.



Now from a practical aspect, if you are expecting rain why carry all that water and if you are not expecting rain, why all the Waterproof = WP gear? ;-))

[pablosl]

Hi,
When I run your code in LB 4.5.1 it gives me an error:

totV = totV + VAL(WORD$$(t$(i), 3, ","))

BASIC Compile Halted: Type Mismatch. Array WORD$$() requires numeric parameters.

-Pablo

[B+]

Oct 5, 2020 18:22:23 GMT pablosl said:

Hi,
When I run your code in LB 4.5.1 it gives me an error:

totV = totV + VAL(WORD$$(t$(i), 3, ","))

BASIC Compile Halted: Type Mismatch. Array WORD$$() requires numeric parameters.

-Pablo

Well your error message pointed right to the problem, as extra $ sign for the WORD$ function.

A last minute change when I capitalized all keywords, sorry. Huh! looks like I missed a ton of other keywords to capitalize (in the SUB). Oh well, I get spoiled by QB64 IDE.

Thanks for heads up, fixed in OP, now. (Retested running the code from a copy/paste.)

[B+]

Ah-ha! A better solution forced by an added item to trip up the original coded solution that should better cover similar problems of this nature:

' Knapsack problem/0-1 Revised 2020-10-13.txt b+
' http://rosettacode.org/wiki/Knapsack_problem/0-1
' These Basic's: Just Basic (or LB), SmallBASIC (not MS Small Basic), QB64 have none posted at Rosetta
' Rosetta Code problem solved 2020-10-04 trans posted at JB under Shared Programs Oct 2020
' https://justbasiccom.proboards.com/thread/563/knapsack-problem-1-rosetta-code

'2020-10-13 revised problem for better code solution
' Here I added a trip to knapsack candidates inventory that forces a better coded solution to cover this case.
' Adding a 3 weight unit object xtra_paper say as backup supplies to "note-case" with a value at 1
' This makes it light enough to fit in Knapsack and it's value is so low it trips up my original code solution.
' 2010-10-13 post improved solution in same thread as above at JB forum.

' Here is the fixed code solution to cover this added case.
' Weight must be < 400 weight units, we want the highest valued items first as they fit.
dim t$(23)   '23 items now to evaluate. see last data item added to trip up original soln.
for i = 1 to 23
   read dat$
   call loadsort dat$
next

'finish solving problem as we printout solution:
print "      *** Knapsack Items sorted by value per unit weight ***"
print " #: item:         wght:  val:   v/w:  packed or not:  accum w:  value packed:"
for i = 1 to 23
   if totw + val(word$(t$(i), 2, ",")) < 400 then
       pack = 1: totw = totw + val(word$(t$(i), 2, ",")): totv = totv + val(word$(t$(i), 3, ","))
   else
       pack = 0
   end if
   print right$(space$(3) + str$(i), 3); space$(1);
   print left$(word$(t$(i), 1, ",") + space$(15), 15);
   print right$(space$(4) + word$(t$(i), 2, ","), 4);
   print right$(space$(6) + word$(t$(i), 3, ","), 6);
   print right$(space$(7) + str$(int(100 * val(word$(t$(i), 3, ",")) / val(word$(t$(i), 2, ",")))/100), 7);
   print space$(4);
   if pack then
       print "packed!"; space$(4);
       print right$(space$(11);totw, 11);
       print right$(space$(15) + str$(totv), 15)
   else
       print "not included."
   end if
next

data "map,9,150"
data "compass,13,35"
data "water,153,200"
data "sandwich,50,160"
data "glucose,15,60"
data "tin,68,45"
data "banana,27,60"
data "apple,39,40"
data "cheese,23,30"
data "beer,52,10"
data "suntan cream,11,70"
data "camera,32,30"
data "t-shirt,24,15"
data "trousers,48,10"
data "umbrella,73,40"
data "wp_trousers,42,70"
data "wp_wear,43,75"
data "note-case,22,80"
data "sunglasses,7,20"
data "towel,18,12"
data "socks,4,50"
data "book,30,10"
data "xtra_paper,3,1"

sub loadsort insert$
   t$(0) = str$(val(t$(0)) + 1) 'track the upper bound in t$(0)
   ub = val(t$(0))
   if ub > 1 then
       for j = 1 to ub - 1
           if val(word$(insert$, 3, ",")) / val(word$(insert$, 2, ","))  > val(word$(t$(j), 3, ","))/ val(word$(t$(j), 2, ",")) then
               for k = ub to j + 1 step -1
                   t$(k) = t$(k - 1)
               next
               exit for
           end if
       next
       t$(j) = insert$
   else
       t$(1) = insert$
   end if
end sub


output:

     *** Knapsack Items sorted by value per unit weight ***
#: item:         wght:  val:   v/w:  packed or not:  accum w:  value packed:
 1 map               9   150  16.66    packed!              9            150
 2 socks             4    50   12.5    packed!             13            200
 3 suntan cream     11    70   6.36    packed!             24            270
 4 glucose          15    60      4    packed!             39            330
 5 note-case        22    80   3.63    packed!             61            410
 6 sandwich         50   160    3.2    packed!            111            570
 7 sunglasses        7    20   2.85    packed!            118            590
 8 compass          13    35   2.69    packed!            131            625
 9 banana           27    60   2.22    packed!            158            685
10 wp_wear          43    75   1.74    packed!            201            760
11 wp_trousers      42    70   1.66    packed!            243            830
12 water           153   200    1.3    packed!            396           1030
13 cheese           23    30    1.3    not included.
14 apple            39    40   1.02    not included.
15 camera           32    30   0.93    not included.
16 towel            18    12   0.66    not included.
17 tin              68    45   0.66    not included.
18 t-shirt          24    15   0.62    not included.
19 umbrella         73    40   0.54    not included.
20 book             30    10   0.33    not included.
21 xtra_paper        3     1   0.33    packed!            399           1031
22 trousers         48    10    0.2    not included.
23 beer             52    10   0.19    not included.


While working this problem I have flashback memories of working this problem that as I recall bluatigro posted probably at the old JB forum. The thing is, we were using brute force method of testing all the combinations of things to bring so this solution is far more elegant.

[B+]

John, tsh73, Rod, and/or Carl

Feel free to run this code by folks at LB as candidate for submission to Rosetta Code to represent JB or Liberty Basic.

Because word$() function is used it is certainly unique to JB or LB.

[tenochtitlanuk]

I suggest you join Rosetta Code ( it is free) and put up the code yourself.

We have always preferred to have solutions shown first here on the forum. This gives it a wide and LB/JB-oriented audience, who may suggest alternatives/improvements, but Rosetta Code is set up as a wiki and anyone can put up solutions- and others may alter or replace them. BUT you can always look at the page's history to see who thinks they know better! Forums only allow you to edit your own entries -administrators have more power of course.

The only caveat is do make sure your code is for LB/JB- we did have problems with a related BASIC being required. And in future we'll have to make plain any LB5-specific code.

Chris Iverson has been very helpful ( as in everything LB) in moderating Rosetta Code. You might like to PM him, or see if he answers on this thread.

I continue to enjoy your contributions..

[tsh73]

I'm sorry to say but as I read here
en.wikipedia.org/wiki/Knapsack_problem#Computational_complexity
Knapsack problem is hard - mathematically hard - so no O(n^p) solution (polinomial execution time from task size) exists.

So just sorting objects by value/weight (O(n^2) execution time or less) just could not give optimal solution in all cases.
It is about as sertain as saying Perpetual motion is not possible.

Right way, IMHO, is dynamic programming - and Rosetta has some really short examples as well.

[B+]

The article talks about several sorts of knapsack problems and if the only method being evaluated is combinations then sure you're stuck by your own rules.

I am pretty sure this method is fine for the given problem where each item can be included or not depending on weight and value, the proof is in the printout of items. Each item is rated by value / weight just go down the sorted list if the item fits include it if not you can't include it so move on. If it can't be done in polynomial time then sorting itself can't be done in polynomial time, it sure has not stopped people from sorting. The only problem I can see arise is if all or any of the value / weight values are the same ie choosing between equally value weighted items.

By the way, I say valuing anything is a very NP problem!

So I'd debate the issue except not on technical level of terminology. Best way to win with me is to show a counter example.
The inability to easily show a counter example kind of proves my point.

[tsh73]

OK OK
I would try and do something - comparing ordering method to a full sareach to see of there is counter examples
I think theer ought to be

Having hard problem is mathematically normal (I'm a bit in it as a higher education teacher)
Dealing with hard problems - to get reasonable (if not perfect) answers in reasonable times - is normal and interesing, too.

(try => tray => wait till sober, later ) )

[B+]

Oct 14, 2020 9:24:23 GMT tenochtitlanuk said:

I suggest you join Rosetta Code ( it is free) and put up the code yourself.

We have always preferred to have solutions shown first here on the forum. This gives it a wide and LB/JB-oriented audience, who may suggest alternatives/improvements, but Rosetta Code is set up as a wiki and anyone can put up solutions- and others may alter or replace them. BUT you can always look at the page's history to see who thinks they know better! Forums only allow you to edit your own entries -administrators have more power of course.

The only caveat is do make sure your code is for LB/JB- we did have problems with a related BASIC being required. And in future we'll have to make plain any LB5-specific code.

Chris Iverson has been very helpful ( as in everything LB) in moderating Rosetta Code. You might like to PM him, or see if he answers on this thread.

I continue to enjoy your contributions..

Well Chris if your reading,... :-)) I'd be pleased if you weigh in.

Actually discussion is what I prefer, I learn nothing or am later embarrassed if I just post code at Rosetta that I think is right and then proved wrong, yikes! no fun or hard learning that way.

I am going to try to come up with counter example and prove tsh73 correct, but it's so hard because that would mean I was wrong ;-))

The first thing I posted I knew was imperfect when I posted because 4 weight units were left and I started playing "What if" game and easily found a problem with the first coded method.

Not so with 2nd refined solution. It is perfect ;-)) Update: No it's NOT!
(No really I have been right once or twice but mathematics can be tricky and anti-intuitive and it takes a true genius to find a demo that can prove something to the open minded specially without mention of logarithms ;-)) eg, primes are infinite and Euclid's proof is genius.)

[B+]

Oct 14, 2020 16:11:15 GMT tsh73 said:

OK OK
I would try and do something - comparing ordering method to a full sareach to see of there is counter examples
I think theer ought to be

Having hard problem is mathematically normal (I'm a bit in it as a higher education teacher)
Dealing with hard problems - to get reasonable (if not perfect) answers in reasonable times - is normal and interesing, too.

(try => tray => wait till sober, later ) )

OK, OK I get it now. I just went shopping, filling up my cart with value priority items and just came up with a combo that my sort and pick method will pass up. Shucks wasn't even that hard to rig.

So tsh73 don't waste another minute on this, and keep up the good work of straightening out your students with bad ideas

I will have this written up later, a little swamped at the moment. Thanks again for your correction.

[B+]

The sort and pick method fails this obvious test with a weight limit of 100

Shopping list:
data "ham,20,25"
data "crackers,100,100"
data "ice cream,20,9"
data "potatoes,70,66"
data "beans,30,17"
data "carrots,20,19"
data "cookies,10,5"


No brainer, almost, just pick the dang crackers for a carry out value of 100.

' Shopping Cart mod of Knapsack problem/0-1 (0-1 means all or nothing bounded problem) b+ 2020-10-14
' Knapsack problem/0-1 Revised 2020-10-13.txt b+
' http://rosettacode.org/wiki/Knapsack_problem/0-1
' These Basic's: Just Basic (or LB), SmallBASIC (not MS Small Basic), QB64 have none posted at Rosetta
' Rosetta Code problem solved 2020-10-04 trans posted at JB under Shared Programs Oct 2020
' https://justbasiccom.proboards.com/thread/563/knapsack-problem-1-rosetta-code

'2020-10-13 revised problem for better code solution
' Here I added a trip to knapsack candidates inventory that forces a better coded solution to cover this case.
' Adding a 3 weight unit object xtra_paper say as backup supplies to "note-case" with a value at 1
' This makes it light enough to fit in Knapsack and it's value is so low it trips up my original code solution.
' 2010-10-13 post improved solution in same thread as above at JB forum.

' Here is the fixed code solution to cover this added case.
' Weight must be < 400 weight units, we want the highest valued items first as they fit.

'2020-10-14 rig up a combo where the sort and pick method fails to optimize the value selection.
' Here is dramatized version of what I do every freakin week with grocery shopping.
' I have to place a very high value on crackers because it is the only thing (nearly) mom at 89 will eat.

' This problem was so easily rigged when I decided the only thing you could pick to get best value of 100
' is crackers. Which a method based on combinations would find, if pure logic failed you.

dim t$(7)   '23 items now to evaluate. see last data item added to trip up original soln.
for i = 1 to 7
   read dat$
   call loadsort dat$
next

'finish solving problem as we printout solution:
print "      *** Shopping Cart Items sorted by value per unit weight ***"
print " #: item:         wght:  val:   v/w:  packed or not:  accum w:  value packed:"
for i = 1 to 7
   if totw + val(word$(t$(i), 2, ",")) <= 100 then
       pack = 1: totw = totw + val(word$(t$(i), 2, ",")): totv = totv + val(word$(t$(i), 3, ","))
   else
       pack = 0
   end if
   print right$(space$(3) + str$(i), 3); space$(1);
   print left$(word$(t$(i), 1, ",") + space$(15), 15);
   print right$(space$(4) + word$(t$(i), 2, ","), 4);
   print right$(space$(6) + word$(t$(i), 3, ","), 6);
   print right$(space$(7) + str$(int(100 * val(word$(t$(i), 3, ",")) / val(word$(t$(i), 2, ",")))/100), 7);
   print space$(4);
   if pack then
       print "packed!"; space$(4);
       print right$(space$(11);totw, 11);
       print right$(space$(15) + str$(totv), 15)
   else
       print "not included."
   end if
next

data "ham,20,25"
data "crackers,100,100"
data "ice cream,20,9"
data "potatoes,70,66"
data "beans,30,17"
data "carrots,20,19"
data "cookies,10,5"

sub loadsort insert$
   t$(0) = str$(val(t$(0)) + 1) 'track the upper bound in t$(0)
   ub = val(t$(0))
   if ub > 1 then
       for j = 1 to ub - 1
           if val(word$(insert$, 3, ",")) / val(word$(insert$, 2, ","))  > val(word$(t$(j), 3, ","))/ val(word$(t$(j), 2, ",")) then
               for k = ub to j + 1 step -1
                   t$(k) = t$(k - 1)
               next
               exit for
           end if
       next
       t$(j) = insert$
   else
       t$(1) = insert$
   end if
end sub


So what is next best? With or without potatoes?

[B+]

Solved (properly) by Combinations method:
'Shopping Cart solve by Combo Method.txt  b+ 2020-10-15
' a combinations problem modeled on a bluatigro post 2016-07-23 and fixed at old JB forum.

maxWeight = 100 'for problem
maxItems = 7  'for data reading and array dimensions
dim item$(maxItems), w(maxItems), v(maxItems)
for i = 1 to maxItems
   read i$, ww, vv
   item$(i) = i$ : w(i) = ww : v(i) = vv
   print item$(i), w(i), v(i)
next
print: print "Find the combination of items above the will fill cart for $100 and maximize the value."
for combo = 1 to (2 ^ (maxItems + 1) - 1)
   scan
   testList$ = "" : testValue = 0 : testWeight = 0
   for power = 0 to maxItems
       if combo and 2 ^ power then
           if testList$ = "" then testList$ = item$(power) else testList$ = testList$ + chr$(10) + item$(power)
           testValue = testValue + v(power)
           testWeight = testWeight + w(power)
       end if
   next
   if testWeight <= maxWeight and testValue >= MaxValue then
       MaxValue = testValue: saveCombo = combo: saveList$ = testList$: saveWeight = testWeight
   end if
   if combo mod 1000 = 0 then locate 1, 1: print space$(20) : locate 1, 1: print combo 'progress
next
print: print "Best value found <= $";maxWeight;" was:"
print saveList$
print "Total $";saveWeight;"  Total value: ";MaxValue

data "ham",20,25
data "crackers",100,100
data "ice cream",20,9
data "potatoes",70,66
data "beans",30,17
data "carrots",20,19
data "cookies",10,5



Output:
ham           20            25
crackers      100           100
ice cream     20            9
potatoes      70            66
beans         30            17
carrots       20            19
cookies       10            5

Find the combination of items above the will fill cart for $100 and maximize the value.

Best value found <= $100 was:
crackers
Total $100  Total value: 100


[B+]

Yeah, I found the code from the old forum and applied it to the Knapsack Problem from Rosetta, here is the code:
' Knapsack problem/0-1 Revised again 2020-10-15.txt b+
' http://rosettacode.org/wiki/Knapsack_problem/0-1
' Found Knapsack problem posed by bluatigro and fixed 2016-07-23 at old JB Forum.
' This code follows that fixed method
' 2020-10-15 revised again because of a base 0, base 1 mixup code was doing 2X's as many calculations as needed.

maxWeight = 400 'for problem
maxItems = 22 'for data reading and array dimensions 8,388,608 combinations!
topItemsIndex = maxItems - 1
DIM item$(topItemsIndex), w(topItemsIndex), v(topItemsIndex)
FOR i = 0 TO topItemsIndex
   READ i$, ww, vv
   item$(i) = i$: w(i) = ww: v(i) = vv
NEXT
topComboIndex = 2 ^ maxItems - 1
FOR combo = 0 TO topComboIndex
   testList$ = "": testValue = 0: testWeight = 0
   FOR power = 0 TO topItemsIndex
       IF combo AND 2 ^ power THEN
           IF testList$ = "" THEN testList$ = item$(power) ELSE testList$ = testList$ + CHR$(10) + item$(power)
           testValue = testValue + v(power)
           testWeight = testWeight + w(power)
       END IF
   NEXT
   IF testWeight <= maxWeight AND testValue >= MaxValue THEN
       MaxValue = testValue
       saveCombo = combo
       saveList$ = testList$
       saveWeight = testWeight
   END IF
   IF combo MOD 1000 = 0 THEN LOCATE 1, 1: PRINT SPACE$(20): LOCATE 1, 1: PRINT combo 'progress
NEXT
CLS
PRINT "Best value found <= "; maxWeight; " was:"
PRINT saveList$
PRINT: PRINT "Total weight: "; saveWeight; "  Total value: "; MaxValue
print "Note: ";topComboIndex + 1;" combinations processed."

DATA "map",9,150
DATA "compass",13,35
DATA "water",153,200
DATA "sandwich",50,160
DATA "glucose",15,60
DATA "tin",68,45
DATA "banana",27,60
DATA "apple",39,40
DATA "cheese",23,30
DATA "beer",52,10
DATA "suntan cream",11,70
DATA "camera",32,30
DATA "T-shirt",24,15
DATA "trousers",48,10
DATA "umbrella",73,40
DATA "WP_trousers",42,70
DATA "WP_wear",43,75
DATA "note-case",22,80
DATA "sunglasses",7,20
DATA "towel",18,12
DATA "socks",4,50
DATA "book",30,10

' Output:
' Best value found <= 400 was:
' map
' compass
' water
' sandwich
' glucose
' banana
' suntan cream
' WP_trousers
' WP_wear
' note-case
' sunglasses
' socks
'
' Total weight: 396  Total value: 1030
' Note: 4194304 combinations processed.



EDIT: Do to a mix-up between what is base 0 eg, powers and array indexes and what is base 1 eg, numbers of things, twice as many calculations were processed than needed. There are 2 ^ 22 combinations of 22 items but original code was doing 2 ^ 23 a difference of 4 million plus calculations! So now, instead of taking 1/2 hour to run it's maybe around 15 minutes.

Sorry one more tiny edit:
FOR power = 0 TO maxItems
changed to
FOR power = 0 TO topItemsIndex

No change in outcome but theoretically speeds up a processing a little and certainly is correct variable to use.

[B+]

tenochtitlanuk:
Chris Iverson has been very helpful ( as in everything LB) in moderating Rosetta Code. You might like to PM him, or see if he answers on this thread.

@chris Iverson or Chris Iverson    (< this forum editor does not help with auto fill?)

So what do you think as keeper of the keys to LB contributions to Rosetta Code (through proper channels anyway).

I think we have a real JB community effort here: bluatigro presents a similar problem years back, his code was fixed and solved (I strongly suspect tsh73 for this part
   FOR power = 0 TO topItemsIndex
       IF combo AND 2 ^ power THEN
which I consider core of solution once you are agree it should be solved by the Combinations method as a best general solution to this sort of problem as bplus realized with his own counter example. I mean look who raised objection to bplus garbage ;-))

Anyway then bplus agitates to get this done through proper channels and get JB / LB properly represented at Rosetta, so he writes it up.

So Chris, I think the ball is in your court ;-))

B+ or @b+   (<< ah now I see it highlighted in blue, message sent)



' Knapsack problem/0-1
' http://rosettacode.org/wiki/Knapsack_problem/0-1
maxWeight = 400 'for problem
maxItems = 22 'for data reading and array dimensions 2^22 combinations!
topItemsIndex = maxItems - 1
DIM item$(topItemsIndex), w(topItemsIndex), v(topItemsIndex)
FOR i = 0 TO topItemsIndex
   READ i$, ww, vv
   item$(i) = i$: w(i) = ww: v(i) = vv
NEXT
topComboIndex = 2 ^ maxItems - 1
FOR combo = 0 TO topComboIndex
   testList$ = "": testValue = 0: testWeight = 0
   FOR power = 0 TO topItemsIndex
       IF combo AND 2 ^ power THEN
           IF testList$ = "" THEN testList$ = item$(power) ELSE testList$ = testList$ + CHR$(10) + item$(power)
           testValue = testValue + v(power)
           testWeight = testWeight + w(power)
       END IF
   NEXT
   IF testWeight <= maxWeight AND testValue >= MaxValue THEN
       MaxValue = testValue
       saveCombo = combo
       saveList$ = testList$
       saveWeight = testWeight
   END IF
   IF combo MOD 1000 = 0 THEN LOCATE 1, 1: PRINT SPACE$(20): LOCATE 1, 1: PRINT combo 'progress
NEXT
CLS
PRINT "Best value found <= "; maxWeight; " was:"
PRINT saveList$
PRINT: PRINT "Total weight: "; saveWeight; "  Total value: "; MaxValue
print "Note: ";topComboIndex + 1;" combinations processed."

DATA "map",9,150
DATA "compass",13,35
DATA "water",153,200
DATA "sandwich",50,160
DATA "glucose",15,60
DATA "tin",68,45
DATA "banana",27,60
DATA "apple",39,40
DATA "cheese",23,30
DATA "beer",52,10
DATA "suntan cream",11,70
DATA "camera",32,30
DATA "T-shirt",24,15
DATA "trousers",48,10
DATA "umbrella",73,40
DATA "WP_trousers",42,70
DATA "WP_wear",43,75
DATA "note-case",22,80
DATA "sunglasses",7,20
DATA "towel",18,12
DATA "socks",4,50
DATA "book",30,10

Someone should at least take it to LB and get it checked out there too! That is if we are still proud to show LB work at Rosetta.