OpenEuphoria

Re: Algorithm Request

• Posted by Pete Lomax <petelomax at blueyonder.co.uk> Apr 08, 2003
• 370 views

On Mon, 7 Apr 2003 16:01:45 -0500, "C. K. Lester" <cklester at yahoo.com>
wrote:

Over ten years ago I wrote a best fit algorithm in COBOL, no less,
without recursion (and plenty of goto statements). I've wanted to
recode it in Euphoria for ages, and now I have.


--
-- Optimised best-fit algorithm
-- Pete Lomax 7th April 2003
--
include sort.e

integer required

sequence sizes
	sizes=3D{377,378,384,387,388,391,396,422,424,425,488,505}

sequence includeset

integer lowbest, lowlevel, highbest, highlevel, worktot, level, item
sequence lowset, highset

procedure display(sequence dtext, integer dtot, sequence dset, integer
dlevel)
integer ib
	printf(1,"%s %d\n",{dtext,dtot})
	for b=3D1 to dlevel do
		ib=3Ddset[b]
		printf(1,"%d  %d\n",{ib,sizes[ib]})
	end for
	if getc(0) then end if
end procedure

procedure find_combination()
--
-- This section tries to find a set of sizes which add up to the
-- required amount exactly.
--
	level=3D1
	lowbest=3D0
	highbest=3D999999999
	item=3Dlength(sizes)
	includeset=3Drepeat(0,item)
	worktot=3D0
	while 1 do
		includeset[level]=3Ditem
		worktot+=3Dsizes[item]
		if worktot=3Drequired then -- Found exact fit
			lowbest=3Dworktot
			lowlevel=3Dlevel
			lowset=3Dincludeset
			return
		end if
		if worktot<required and worktot > lowbest then
			lowbest=3Dworktot
			lowlevel=3Dlevel
			lowset=3Dincludeset
		end if
		if item > 1 -- More to be tested
		and worktot<required then
			item-=3D1
			level+=3D1 -- Leave item in table;
		else
			if worktot>required and worktot < highbest then
				highbest=3Dworktot
				highlevel=3Dlevel
				highset=3Dincludeset
			end if
			while 1 do
				--
				-- Now we need to backtrack;  remove item from running
				-- total and look at the next instead.
				--
				worktot-=3Dsizes[item]
				if item > 1 then -- More to be tested
					item-=3D1 -- Look at next (overwrite item in table)
					exit
				end if
				--
				-- We have exhausted all possibilities at this level;=20
				-- backtrack to a previous level.
				--
				includeset[level]=3D0
				level-=3D1
				if level=3D0 then return end if -- All done
				item=3Dincludeset[level]
			end while
		end if
	end while
end procedure

procedure main()
	required=3D0

	for i=3D1 to length(sizes) do
		required+=3Dsizes[i]
	end for
	required=3Dfloor(required/2)
	printf(1,"Required: %d\n",{required})

	sizes=3Dsort(sizes)
	find_combination()
	if lowbest=3Drequired then
		display("Exact fit",lowbest,lowset,lowlevel)
	else
		display("Lower figure",lowbest,lowset,lowlevel)
		display("Higher figure",highbest,highset,highlevel)
	end if
end procedure

	main()