No such thing as a small change PerlMonks

### Re: Puzzle: need a more general algorithm

by japhy (Canon)
 on Jul 08, 2002 at 19:59 UTC ( #180300=note: print w/replies, xml ) Need Help??

in reply to Puzzle: need a more general algorithm

Here's the algorithm:
use constant COL => 4; my @data = qw( 10 15 25 30 10 13 ); my @cols = map [\$_], @data; while (@data > COL) { my \$i = 0; my \$s = \$data[\$i] + \$data[\$i+1]; for my \$j (1 .. @data-2) { (\$i, \$s) = (\$j, \$data[\$j] + \$data[\$j+1]) if \$data[\$j] + \$data[\$j+1] < \$s; } splice @data, \$i, 2, \$s; splice @cols, \$i, 2, [@{ \$cols[\$i] }, @{ \$cols[\$i+1] }]; }

_____________________________________________________
Jeff[japhy]Pinyan: Perl, regex, and perl hacker, who'd like a job (NYC-area)
s++=END;++y(;-P)}y js++=;shajsj<++y(p-q)}?print:??;

Replies are listed 'Best First'.
Re: Re: Puzzle: need a more general algorithm
by Anonymous Monk on Jul 08, 2002 at 23:28 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.
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

Create A New User
Node Status?
node history
Node Type: note [id://180300]
help
Chatterbox?
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others pondering the Monastery: (4)
As of 2018-06-19 01:13 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
Should cpanminus be part of the standard Perl release?

Results (111 votes). Check out past polls.

Notices?