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 .. @data2) {
($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 (NYCarea)
s++=END;++y(;P)}y js++=;shajsj<++y(pq)}?print:??;
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.  [reply] 

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 NPHard)? 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] 
