Re: Numbers problem
- Posted by mistertrik at hotmail.com Jul 13, 2002
- 358 views
Try this: It's like a tree approach... and redundant and over-the-limit trees are removed to make it faster.... So, you have {7,10,24} and you want to get 44, for example. ( # = removed ) | | { } (time) / | \ | {7} {10} {24} \|/ / | \ / | \ / | \ {7,7} {7,24} {7,10} (#) {10,10} {10,24} (#) (#) {24,24} and so forth. Add another field to the element to keep a running total, and voila! See code below..... ===================================================== .______<-------------------\__ / _____<--------------------__|=== ||_ <-------------------/ \__| Mr Trick --This example grows an array of totals... --for each element, the first entry, added together, equals the second. --ie state 1 -> { {{101},101}, {{65},65},.... -- state 2 -> { {{101,101},202}, {{101,65},166}, {{65,65},130},... -- state 3 -> { {{101,101,101},303}, {{101,101,65},267}, {{101,101,40},242}..... --etc --until an instance temp[a][2] is equal to the target. if this never happens, --then it returns not found. include sort.e sequence numbers atom target, k sequence data, temp numbers = {101,65,40,31} --or whatever. (if you can, avoid small numbers target = 1001 --and high targets.) --function to remove all duplicate elements from a sequence function trim(sequence s) sequence d d = {} for a = 1 to length(s) do if not find(s[a],d) then d &= {s[a]} end if end for return d end function temp = {{{},0}} --starts as blank (0) while 1 do data = trim(temp) --copy the next dataset to the current dataset --taking out any reduntant variables temp = {} --set up for the next run k = 0 for a = 1 to length(data) do --for each element of the current dataset if data[a][2] < target then --if the total isn't already over the target for b = 1 to length(numbers) do --for each number temp &= {data[a]} --copy a current element into the next dataset k += 1 temp[k][1] = sort(temp[k][1] & numbers[b]) --sort the constituents temp[k][2] += numbers[b] -- and add that number if temp[k][2] = target then --if the new total is the target... puts(1,"Found: if you add ") --do print(1,temp[k][1]) --a printf(1," you get %d",{temp[k][2]}) --little abort(0) --dance. end if end for end if end for --any elements that were over the limit did not get copied to the next --state.... so if they all are: if not length(temp) then puts(1,"No matches") --doodums. abort(0) end if end while --<end>-- >From: akusaya at gmx.net >Reply-To: EUforum at topica.com >To: EUforum <EUforum at topica.com> >Subject: Numbers problem >Date: Fri, 12 Jul 2002 09:43:22 -0500 > > >I have a programmin problem. > >Suppose I have 3 integer numbers: 7, 10, 24. > >The problem is how to get an integer number by summing any of the numbers >above. > >Example: to get 44 use 10 10 24. > to get 41 use 7 10 24. > >I see on many websites it is called knapsack problem. But I don\'t >understand the explanations on many websites I found. > >Please help me, ASAP because I need it very much. > >Thanks very much!! > > > >