Python: How to get all possible bin combinations from a set of data with a weight limit?

Question

I have a list of numbers which all correspond to items of different weight:

weights = [50, 40, 30, 100, 150, 12, 150, 10, 5, 4]

I need to split the values into two bins with the caveat that the bin sum total cannot exceed 300.

e.g. The simplest one I can think of is:

bin1 = [150, 150] = 300
bin2 = [50, 40, 30, 100, 12, 10, 5, 4] = 251

I want to be able to get all the combinations of these weights that would satisfy this caveat, unsure how to go about this?

Answer 1

one way is brute-forcing it by binning all possible permutations of the list

there has to be a better (more clever) way of doing that - it's terribly slow. (but I'm supposed to be doing other things right now ;-))

from itertools import permutations

max_bin_size = 300
weights = [50, 40, 30, 100, 150, 12, 150, 10, 5, 4]

bin_combinations = set()

def to_bins(weights):
    bin = []
    for weight in weights:
        if weight > max_bin_size:
            raise ValueError("wtf?")
        if sum(bin) + weight > max_bin_size:
            yield tuple(sorted(bin))
            bin = [weight]
        else:
            bin.append(weight)
    yield tuple(sorted(bin))


for permutation in set(permutations(weights)):
    bin_combinations.add(tuple(sorted(to_bins(permutation))))

for combination in bin_combinations:
    print(combination)

# ((4, 10, 40, 100), (5, 12, 150), (30, 50, 150))
# ((4, 5, 10, 40, 50, 100), (12, 30), (150, 150))
# ((4, 10, 30, 150), (5, 50, 100), (12, 40, 150))
# ((4, 5, 30, 100), (10, 50, 150), (12, 40, 150))
# ((4, 12, 50, 100), (5, 10, 30, 40), (150, 150))
# ((4, 5, 150), (10, 30, 40, 150), (12, 50, 100))
# ...

Update:

a version with reuse of bins (assuming one can put the weights freely into any available bin):

from itertools import permutations

max_bin_size = 300
weights = [50, 40, 30, 100, 150, 12, 150, 10, 5, 4]

bin_combinations = set()


def to_bins(weights):
    bins = [[]]
    for weight in weights:
        if weight > max_bin_size:
            raise ValueError("wtf?")
        for bin in bins:
            if sum(bin) + weight > max_bin_size:
                continue
            bin.append(weight)
            break
        else:
            bins.append([weight])            
    return tuple(sorted(tuple(sorted(bin)) for bin in bins))


for permutation in set(permutations(weights)):
    bin_combinations.add(to_bins(permutation))

print(len(bin_combinations), "combinations")
for combination in bin_combinations:
    print(combination)

# 14 combinations
# ((4, 5, 10, 12, 30, 50, 150), (40, 100, 150))
# ((4, 5, 10, 30, 40, 50, 150), (12, 100, 150))
# ((4, 12, 30, 100, 150), (5, 10, 40, 50, 150))
# ((4, 100, 150), (5, 10, 12, 30, 40, 50, 150))
# ((4, 5, 12, 30, 50, 150), (10, 40, 100, 150))
# ((4, 5, 10, 12, 100, 150), (30, 40, 50, 150))
# ((4, 5, 12, 30, 40, 50, 150), (10, 100, 150))
# ((4, 5, 40, 100, 150), (10, 12, 30, 50, 150))
# ((4, 10, 12, 30, 40, 50, 150), (5, 100, 150))
# ((4, 5, 10, 30, 100, 150), (12, 40, 50, 150))
# ((4, 5, 10, 12, 30, 40, 150), (50, 100, 150))
# ((4, 10, 40, 50, 150), (5, 12, 30, 100, 150))
# ((4, 5, 10, 12, 40, 50, 150), (30, 100, 150))
# ((4, 5, 10, 12, 30, 40, 50, 100), (150, 150))