Beefy Boxes and Bandwidth Generously Provided by pair Networks
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 ( [id://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

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://180300]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others musing on the Monastery: (3)
As of 2024-03-19 04:20 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found