Beefy Boxes and Bandwidth Generously Provided by pair Networks
XP is just a number
 
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
Download Code
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?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others making s'mores by the fire in the courtyard of the Monastery: (5)
As of 2014-12-29 04:17 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    Is guessing a good strategy for surviving in the IT business?





    Results (184 votes), past polls