OpenEuphoria

RE: Numbers problem

• Posted by aku saya <akusaya at gmx.net> Jul 15, 2002
• 393 views

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
> 
>