"be consistent" 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] }];
}
[download]```

_____________________________________________________
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

Log In?
 Username: Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://180300]
help
Chatterbox?
 [nettop]: need to hire a PERL programmer [shmem]: conditions? [shmem]: tell them

How do I use this? | Other CB clients
Other Users?
Others exploiting the Monastery: (7)
As of 2018-04-20 17:20 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
My travels bear the most uncanny semblance to ...

Results (77 votes). Check out past polls.

Notices?