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!)