OpenEuphoria

Re: Numbers problem

• Posted by petelomax at blueyonder.co.uk Jul 12, 2002
• 348 views

On Fri, 12 Jul 2002 09:43:22 -0500, akusaya at gmx.net wrote: 
 
>======== The Euphoria Mailing List ========  
> 
>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 
testsetrepeat(0,length(numset)) 
testidx=1 
testtot0 
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 
		setsfound0		-- 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 
				setsfound1	-- 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