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!