|
Post by B+ on Oct 5, 2020 4:53:00 GMT
reference: rosettacode.org/wiki/Knapsack_problem/0-1You 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? ;-))
|
|
|
Post by pablosl on Oct 5, 2020 18:22:23 GMT
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
|
|
|
Post by B+ on Oct 5, 2020 18:48:16 GMT
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.)
|
|
|
Post by B+ on Oct 13, 2020 19:09:59 GMT
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.
|
|
|
Post by B+ on Oct 13, 2020 19:27:57 GMT
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.
|
|
|
Post by tenochtitlanuk on Oct 14, 2020 9:24:23 GMT
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..
|
|
|
Post by tsh73 on Oct 14, 2020 12:28:50 GMT
I'm sorry to say but as I read here en.wikipedia.org/wiki/Knapsack_problem#Computational_complexityKnapsack 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.
|
|
|
Post by B+ on Oct 14, 2020 16:04:02 GMT
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.
|
|
|
Post by tsh73 on Oct 14, 2020 16:11:15 GMT
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 ) )
|
|
|
Post by B+ on Oct 14, 2020 16:24:40 GMT
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.)
|
|
|
Post by B+ on Oct 14, 2020 19:37:36 GMT
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.
|
|
|
Post by B+ on Oct 14, 2020 20:48:31 GMT
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?
|
|
|
Post by B+ on Oct 15, 2020 5:47:25 GMT
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
|
|
|
Post by B+ on Oct 15, 2020 6:29:35 GMT
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.
|
|
|
Post by B+ on Oct 16, 2020 17:22:10 GMT
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.
|
|