1. RE: Numbers problem
> -----Original Message-----
> From: akusaya at gmx.net [mailto:akusaya at gmx.net]
> 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.
Art Adamson wrote a knapsack program (search for 'knapsack' in the archives)
that's close to what you need. I'd written my own a while back. I'll see
if I can dig it up.
Matt Lewis
2. RE: Numbers problem
The knapsack in the archives is very different.
it uses float numbers and the goal is seek as close as possible. But I
need the exact sum..
Thanks...
Matthew Lewis wrote:
>
> > -----Original Message-----
> > From: akusaya at gmx.net [mailto:akusaya at gmx.net]
>
> > 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.
>
> Art Adamson wrote a knapsack program (search for 'knapsack' in the
> archives)
> that's close to what you need. I'd written my own a while back. I'll
> see
> if I can dig it up.
>
> Matt Lewis
>
>
3. RE: Numbers problem
Thanks very much, this is the best and fast!
petelomax at blueyonder.co.uk wrote:
> On Fri, 12 Jul 2002 09:43:22 -0500, akusaya at gmx.net wrote:
>
> >
> >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.
>
> Neither do I, but the following seems to work:
>
> --#
> --# Program to find the set of numbers which add to a specified total.
> --# Eg given a set of 7, 10, 24, we want to find what sums to 44: in
> this case 10+10+24.
> --#
>
> sequence numset
> numset = {7,10,24}
> --# you will probably find the first set faster if numset is sorted
> highest first.
> integer target
> target = 44
>
> procedure printsets()
> sequence testset -- holds eg {0,2,1} for (7*0+)10*2+24=44
> integer testidx, testtot, setsfound
> testset=repeat(0,length(numset))
> testidx=1
> testtot=0
> setsfound=0 -- true/false/"+" required in display flag
> while 1 do
> while testidx<=length(numset) do
> --# you may or may not get much better performance here using
> floor((target-testtot)/numset[testidx])
> if target-testtot>=numset[testidx] then
> testtot+=numset[testidx]
> testset[testidx]+=1
> else
> testidx+=1
> end if
> end while
> if testtot=target then -- set found
> setsfound=0 -- to put "+" in display
> for i = 1 to length(numset) do
> if testset[i] then
> if setsfound then puts(1,"+") end if
> printf(1,"%d",numset[i])
> if testset[i]>1 then
> printf(1,"*%d",testset[i])
> end if
> setsfound=1 -- skip "no sets found" message
> end if
> end for
> printf(1,"=%d\n",target)
> end if
> --#
> --# backtrack; remove last entry in testset
> --#
> testidx-=1
> while testidx do
> if testset[testidx] then
> testset[testidx]-=1
> testtot-=numset[testidx]
> testidx+=1
> exit -- backtrack done, carry on
> end if
> testidx-=1
> end while
> if testidx=0 then exit end if -- no set exists (or no more
> sets exist)
> end while
> if setsfound=0 then
> puts(1,"no set exists")
> end if
> end procedure
>
> printsets()
> if getc(0) then end if
>
>
> Pete
>
>
