OpenEuphoria

Re: Numbers problem

• Posted by mistertrik at hotmail.com Jul 13, 2002
• 480 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!!
>
>
>
>