On Wed, Nov 24, 2010 at 8:34 AM, Tom Boland <t...@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 -- http://mail.python.org/mailman/listinfo/python-list
