How would you evenly distribute a list of sublists that each have a numerical value across three lists?

How would you evenly distribute a list of sublists that each have a value?

I'd like to distribute the following list into 3 lists.

lst = [['a',10],['b',40],['c',10],['d',30],['e',20],['f',100],['g',90],['h',4]]

Since the aggregate of all the values is 304, the three lists should aggregate to about 101.3.

This is the result I'd like to produce in some form.

lst1 = [['g',90],['a',10]]
lst2 = [['f',100],['h',4]]
lst3 = [['b',40],['c',10],['d',30],['e',20]]

This is the solution I have so far that addresses it but needs some work to make it faster.

def ListSum(lst):
    lst = map(lambda subli: subli[1],lst)
    return sum(lst)

def EvenlyDistribute(lst):
    #put into bucket until reached, then move to the next bucket
    Lst1 = []
    Lst2 = []
    Lst3 = []
    for subli in lst:
        try:
            if ListSum(Lst1) < 100:
                Lst1.append(subli)
            elif ListSum(Lst2) < 100:
                Lst2.append(subli)
            else:
                Lst3.append(subli)
        except:
            pass
    print Lst1
    print Lst2
    print Lst3

Solution

Here's a simple implementation. First, sort the input list by weight, then enumerate, adding each item to the least full bucket.

def EvenlyDistribute(lst, n):
    """Distribute items in lst (tuples of (val, weight)) into n buckets"""
    buckets = [[] for i in range(n)]
    weights = [[0, i] for i in range(n)]
    for item in sorted(lst, key=lambda x: x[1], reverse=True):
        idx = weights[0][1]
        buckets[idx].append(item)
        weights[0][0] += item[1]
        weights = sorted(weights)
    return buckets

for i, v in enumerate(EvenlyDistribute(lst, 3)):
    print(v)

returns

[['f', 100], ['h', 4]]
[['g', 90], ['a', 10]]
[['b', 40], ['d', 30], ['e', 20], ['c', 10]]