Beefy Boxes and Bandwidth Generously Provided by pair Networks
P is for Practical

Re(2): Puzzle: need a more general algorithm

by FoxtrotUniform (Prior)
on Jul 08, 2002 at 20:37 UTC ( #180317=note: print w/replies, xml ) Need Help??

in reply to Re: Puzzle: need a more general algorithm
in thread Puzzle: need a more general algorithm

Keep in mind that this is a weighted distribution: three categories with weight 10 are worth one category with weight 30 (so if N=2, you'd want 3/1 rather than 2/2).

This looks to me like a constrained (order must not change) variant on the bin packing problem. Bin packing is NP-complete in the general case (IIRC), but the order constraint makes this quite tractable (see merlyn's typesetting comment). This problem has a rather good (n lg n or n^2) solution via dynamic programming: the typesetting problem was on one of my assignments in an advanced algorithms class. (Hey, did Ovid just post a homework problem? ;-b) I'll dig through my old notes when I get home from work and see if I can find it. In the mean time, you (Ovid) might look at Text::Format for ideas.

Update: D'oh! Another constraint on the text formatting problem that isn't present here is a maximum on line length (bin size), which makes it hard to reject a bogus solution (too much in one bin) quickly. On the other hand, this solution is constrained by number of bins, which the text formatting solution isn't. Hmm.... (Great problem, Ovid!)

The hell with paco, vote for Erudil!

  • Comment on Re(2): Puzzle: need a more general algorithm

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://180317]
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others musing on the Monastery: (5)
As of 2017-10-22 15:50 GMT
Find Nodes?
    Voting Booth?
    My fridge is mostly full of:

    Results (273 votes). Check out past polls.