efficient way of splitting a list in to lists where the sum of the values in each does not exceed n

[Ian Kelly]

On Wed, Nov 24, 2010 at 8:34 AM, Tom Boland <tom at t0mb.net> wrote:
> I'm trying to find a _nice_ way of taking a list of integers, and splitting
> them in to lists where the sum of the values does not exceed a threshold.
>
> for instance:
>
> l = [1, 2, 3, 4, 5, 6]
> n = 6
>
> nl = [1,2,3], [4], [5], [6]
>
>
> I don't mind if it's done like playing blackjack/pontoon (the card game
> where you try not to exceed a total of 21), ie. going through the list
> sequentially, and splitting off the list as soon as the running total would
> exceed n.  A way of efficiently making all lists as close to n as possible
> would be nice however.

You've described the bin-packing problem [1].  It's known to be
NP-hard, so you won't find a solution that is both efficient and
optimal, although the Wikipedia page mentions some polynomial-time
approximate algorithms that you might want to take a look at.

Cheers,
Ian

[1] http://en.wikipedia.org/wiki/Bin_packing_problem