|
Post by Rod on Oct 16, 2020 19:44:25 GMT
There is no Just BASIC section on Rosetta. Just BASIC is part of the Liberty BASIC family. If we have coded a solution to a problem then post it. Post it under Liberty BASIC.
Rosetta is an open repository and no single person manages it, certainly Chris will help but if you have a solution post it. If others think it is flawed or could be improved that is the nature of Rosetta.
|
|
|
Post by tsh73 on Oct 20, 2020 15:02:59 GMT
Sorry for being really slow, but by moving string operations out of main loop it could be sped up a bit ( also I tried * using pre-calculated array b(i) insread of 2^i * try to cut power loop (exit for) if testWeight already more then maxWeight but did not got any meaningful difference )
But this is brute search. Way to make problem soleve faster is to use some other algorythm.
' 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! 'maxItems = 17 topItemsIndex = maxItems - 1 DIM item$(topItemsIndex), w(topItemsIndex), v(topItemsIndex)
t0=time$("ms") 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 testValue = testValue + v(power) testWeight = testWeight + w(power) END IF NEXT IF testWeight <= maxWeight AND testValue >= MaxValue THEN MaxValue = testValue saveCombo = combo END IF IF combo MOD 1000 = 0 THEN LOCATE 1, 1: PRINT SPACE$(20): LOCATE 1, 1: PRINT combo 'progress NEXT
'put string ops off main loop. 'decode saved combo here, once saveList$="" saveWeight =0 FOR power = 0 TO topItemsIndex IF saveCombo AND 2 ^ power THEN IF saveList$ = "" THEN saveList$ = item$(power) ELSE saveList$ = saveList$ + CHR$(10) + item$(power) saveWeight = saveWeight + w(power) END IF NEXT
t1=time$("ms") CLS PRINT "Best value found <= "; maxWeight; " was:" PRINT saveList$ PRINT: PRINT "Total weight: "; saveWeight; " Total value: "; MaxValue print "Note: ";topComboIndex + 1;" combinations processed." print "Time taken " ;t1-t0 '14443 for n=17, 9902 after taking string ops out '391602s for n = 22 on fast machine, or 6.5 minutes
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
|
|
|
Post by B+ on Oct 20, 2020 15:41:43 GMT
It does make sense to process one Combo List string at the end of the run, instead of 4 Million plus during the run. ;-)) ha! had that but someone said "No, not good for general solution." I said, "Show me a counter example." Then I said, "Oh wait, I found one myself. It is too easy to rig one up to defeat anything but brute force." Perhaps if someone can say, "Well you can use the shortcut originally posted under such and such conditions." That may be worthy of a genius award. Say, BTW, I used the Combo Method to find the optimum Gin Hand. I spent hours and hours trying a rules / conditions based thing and kept getting lost in complexity in trying to handle all the cases that could arise no matter how rare. With combos method it whipped up a best solution every time with minimum coding because it tests every possible way you can use cards that could be played in both in a 3 or 4 of-a-kind set or in a Straight set (sequence set, same suit) but you are allowed only one or the other. At first I used combo tables in separate data files. Then I found this method of combo generating, JIT processing, and I could dump the data files and use run time generated combos as needed. Nice! PS, hmm... can save more time be saved by using a Combo Table that has the 4 Million combos already calculated? Seems kind of like desperate attempt to solve a specific problem instead of finding a solid approach to the general problem. Oh, just had a thought, you can rule OUT! one, two, three... n item solutions depending on weights ie if no item weighs more than 1/n th of total weight allowed then you must have at least n items in the solution, that could make significantly less combos to test. I may get genius award yet! EDIT: missing a crucial word rule OUT!
|
|
|
Post by B+ on Oct 20, 2020 17:32:42 GMT
Update: shoot! dang water weighs twice as much as anything else! only eliminates 1 or 2 items. But we can do much better than that!
|
|
|
Post by Rod on Oct 20, 2020 18:10:21 GMT
I saw it as a sorting problem, pack the most worthy stuff till you get to the limit. What am I not seeing?
dim item$(24) dim pack(24,4) for n= 1 to 22 read i$,w,v item$(n)=i$ pack(n,1)=n pack(n,2)=w pack(n,3)=v pack(n,4)=v/w next
sort pack(,22,1,4 wt=0 for n= 1 to 22 wt=wt+pack(n,2) if wt<400 then print item$(pack(n,1)),wt next wait
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 "waterproof trousers",42,70 data "waterproof overclothes",43,75 data "note-case",22,80 data "sunglasses",7,20 data "towel",18,12 data "socks",4,50 data "book",30,10
|
|
|
Post by B+ on Oct 20, 2020 19:34:51 GMT
I saw it as a sorting problem, pack the most worthy stuff till you get to the limit. What am I not seeing? dim item$(24) dim pack(24,4) for n= 1 to 22 read i$,w,v item$(n)=i$ pack(n,1)=n pack(n,2)=w pack(n,3)=v pack(n,4)=v/w next
sort pack(,22,1,4 wt=0 for n= 1 to 22 wt=wt+pack(n,2) if wt<400 then print item$(pack(n,1)),wt next wait
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 "waterproof trousers",42,70 data "waterproof overclothes",43,75 data "note-case",22,80 data "sunglasses",7,20 data "towel",18,12 data "socks",4,50 data "book",30,10
Well that's how I saw it originally but that method wont work for this list and weight (or dollar) limit of 100 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" Best value you could put in shopping cart is crackers. So the sort method does not work every time as a general solution to this kind of problem. Also this from tsh73 Oct 14, 2020 this thread:
|
|
|
Post by B+ on Oct 20, 2020 21:39:06 GMT
Checking if have minimum amount of items actually takes longer!!!
' picking up from tsh73 mod 2020-10-20 saving the string list processing until end ' Knapsack problem/0-1 ' http://rosettacode.org/wiki/Knapsack_problem/0-1
' b+ 2020-10-20 ' Oh, just had a thought, you can rule OUT! one, two, three... n item solutions ' depending on weights ie if no item weighs more than 1/n th of total weight ' allowed then you must have at least n items in the solution, that could make ' significantly less combos to test. I may get genius award yet! :)
' 12.21 Minutes to run the combinations before tsh73 mod. ' With tsh73 mod: 488.245 sec = 8.13 mins ' After: test for minItems 528.001 = 8.8 mins ' 2nd After: (turned off Browser) 540.904 mins = 9.01 worse and WORSE! ' 3rd test: 530.875 = 8.85
' so tsh73 verison not checking for minItems is fastest.
' 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! 'maxItems = 17 topItemsIndex = maxItems - 1 DIM item$(topItemsIndex), w(topItemsIndex), v(topItemsIndex), sortWeights(maxItems)
t0=time$("ms") FOR i = 0 TO topItemsIndex READ i$, ww, vv item$(i) = i$: w(i) = ww: v(i) = vv call loadSort ww 'make a list of weights from most to least NEXT
' best (or worse?) case scenerio the heaviest things also are most valued ' so we MUST take a certain Minimum number of items for i = 1 to maxItems 'check the list if sortWeights(i) < maxWeight then 'sorry can take that! if totalWeight + sortWeights(i) <= maxWeight then minItems = minItems + 1 ' OK this wont break the camel's back totalWeight = totalWeight + sortWeights(i) end if end if print i, sortWeights(i), totalWeight next print " Minimum items we must take ";minItems
topComboIndex = 2 ^ maxItems - 1 FOR combo = 0 TO topComboIndex testList$ = "": testValue = 0: testWeight = 0 : itemCount = 0 FOR power = 0 TO topItemsIndex IF combo AND 2 ^ power THEN itemCount = itemCount + 1 testValue = testValue + v(power) testWeight = testWeight + w(power) END IF NEXT if itemCount >= minItems then IF testWeight <= maxWeight AND testValue >= MaxValue THEN MaxValue = testValue saveCombo = combo END IF end if IF combo MOD 1000 = 0 THEN LOCATE 1, 27: PRINT SPACE$(20): LOCATE 1, 25: PRINT combo 'progress NEXT
'put string ops off main loop. 'decode saved combo here, once saveList$="" saveWeight =0 FOR power = 0 TO topItemsIndex IF saveCombo AND 2 ^ power THEN IF saveList$ = "" THEN saveList$ = item$(power) ELSE saveList$ = saveList$ + CHR$(10) + item$(power) saveWeight = saveWeight + w(power) END IF NEXT
t1=time$("ms") CLS PRINT "Best value found <= "; maxWeight; " was:" PRINT saveList$ PRINT: PRINT "Total weight: "; saveWeight; " Total value: "; MaxValue print "Note: ";topComboIndex + 1;" combinations processed." print "Time taken " ;t1-t0 '14443 for n=17, 9902 after taking string ops out '391602s for n = 22 on fast machine, or 6.5 minutes
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 'change book from 30 to 3 to test code
SUB loadSort insert sortWeights(0) = sortWeights(0) + 1 'track the upper bound in sortWeights(0) ub = sortWeights(0) IF ub > 1 THEN FOR j = 1 TO ub - 1 IF insert > sortWeights(j) THEN FOR k = ub TO j + 1 STEP -1 sortWeights(k) = sortWeights(k - 1) NEXT exit for END IF NEXT sortWeights(j) = insert ELSE sortWeights(1) = insert END IF END SUB
|
|