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!
Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
Read Where should I post X? if you're not absolutely sure you're posting in the right place.
Please read these before you post! —
Posts may use any of the Perl Monks Approved HTML tags:
You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
- a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
Link using PerlMonks shortcuts! What shortcuts can I use for linking?
See Writeup Formatting Tips and other pages linked from there for more info.
| & || & |
| < || < |
| > || > |
| [ || [ |
| ] || ] ||