There's more than one way to do things 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:??;

Comment on Re: Puzzle: need a more general algorithm
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 the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others imbibing at the Monastery: (19)
As of 2015-08-04 14:41 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?