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

Tom Boland tom at t0mb.net
Wed Nov 24 17:52:59 CET 2010

```Thanks for the reply Ian,

I've looked in to the bin-packing problem in a general sense now, and I
think my ugly algorithm is actually not too bad (although not too
efficient either!) :)

It was only for a quick job any how.

Thanks again.  Tom.

On 24/11/10 16:16, Ian Kelly wrote:
> 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