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

[Tom Boland]

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