Re: Re: Puzzle: need a more general algorithm

Greediness does not work in general. What if your categories have sizes 15, 15, 10, 10, 15, 15? Your solution comes out with a suboptimal answer.

Comment on Re: Re: Puzzle: need a more general algorithm

Replies are listed 'Best First'.
Re(3): Puzzle: need a more general algorithm by FoxtrotUniform (Prior) on Jul 08, 2002 at 23:42 UTC
Greediness does not work in general. What if your categories have sizes 15, 15, 10, 10, 15, 15? Your solution comes out with a suboptimal answer. That's what backtracking's for. :-) Actually, that brings up an interesting question: Ovid, are there any bounds on how optimal the answer has to be? Exactly optimal (sucky if this problem turns out to be NP-Hard)? Within a constant factor of optimal (like, max length no more than 1.5x larger than optimal)? `-- The hell with paco, vote for Erudil! :wq`	[reply]

Replies are listed 'Best First'.

Re(3): Puzzle: need a more general algorithm
by FoxtrotUniform (Prior) on Jul 08, 2002 at 23:42 UTC

Greediness does not work in general. What if your categories have sizes 15, 15, 10, 10, 15, 15? Your solution comes out with a suboptimal answer.

That's what backtracking's for. :-)

Actually, that brings up an interesting question: Ovid, are there any bounds on how optimal the answer has to be? Exactly optimal (sucky if this problem turns out to be NP-Hard)? Within a constant factor of optimal (like, max length no more than 1.5x larger than optimal)?

-- The hell with paco, vote for Erudil! :wq

[reply]