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
> 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
>
More information about the Python-list
mailing list