Brute force multiple subset sum solution

mssp.py

from collections import OrderedDict
from pprint import pprint

def greedy_reduction(weights, capacities):
    weights = [{'weight': weight, 'used': False} for weight in sorted(weights, reverse = True)]
    knapsacks = [{'capacity': capacity, 'load': 0, 'weights': []} for capacity in sorted(capacities, reverse = True)]

    for knapsack in knapsacks:
        for weight in weights:
            if weight['used']:
                continue

            if knapsack['load']:
                effective_weight = weight['weight'] + 0.125
            else:
                effective_weight = weight['weight']

            if knapsack['capacity'] - knapsack['load'] >= effective_weight:
                weight['used'] = True
                knapsack['load'] += effective_weight
                knapsack['weights'].append(weight['weight'])

    return weights, knapsacks


def main():
    weights = [53.75 - (n * 0.75) for n in range(32)] + [50.25 - (n * 0.75) for n in range(32)]
    capacities = [96] * 9 + [72] * 25 + [54]
    weights, knapsacks = greedy_reduction(weights, capacities)
    print("Unused Weights:")
    pprint([weight for weight in weights if weight['used'] == False])
    print("Knapsacks:")
    pprint(knapsacks)

if __name__ == '__main__':
    main()

"""
Unused Weights:
[{'used': False, 'weight': 35.75}]
Knapsacks:
[{'capacity': 96, 'load': 95.875, 'weights': [53.75, 42.0]},
 {'capacity': 96, 'load': 95.875, 'weights': [53.0, 42.75]},
 {'capacity': 96, 'load': 95.875, 'weights': [52.25, 43.5]},
 {'capacity': 96, 'load': 95.875, 'weights': [51.5, 44.25]},
 {'capacity': 96, 'load': 95.875, 'weights': [50.75, 45.0]},
 {'capacity': 96, 'load': 95.875, 'weights': [50.25, 45.5]},
 {'capacity': 96, 'load': 95.875, 'weights': [50.0, 45.75]},
 {'capacity': 96, 'load': 95.875, 'weights': [49.5, 46.25]},
 {'capacity': 96, 'load': 95.875, 'weights': [49.25, 46.5]},
 {'capacity': 72, 'load': 48.75, 'weights': [48.75]},
 {'capacity': 72, 'load': 48.5, 'weights': [48.5]},
 {'capacity': 72, 'load': 48.0, 'weights': [48.0]},
 {'capacity': 72, 'load': 47.75, 'weights': [47.75]},
 {'capacity': 72, 'load': 47.25, 'weights': [47.25]},
 {'capacity': 72, 'load': 47.0, 'weights': [47.0]},
 {'capacity': 72, 'load': 71.875, 'weights': [44.75, 27.0]},
 {'capacity': 72, 'load': 71.875, 'weights': [44.0, 27.75]},
 {'capacity': 72, 'load': 71.875, 'weights': [43.25, 28.5]},
 {'capacity': 72, 'load': 71.875, 'weights': [42.5, 29.25]},
 {'capacity': 72, 'load': 71.875, 'weights': [41.75, 30.0]},
 {'capacity': 72, 'load': 71.875, 'weights': [41.25, 30.5]},
 {'capacity': 72, 'load': 71.875, 'weights': [41.0, 30.75]},
 {'capacity': 72, 'load': 71.875, 'weights': [40.5, 31.25]},
 {'capacity': 72, 'load': 71.875, 'weights': [40.25, 31.5]},
 {'capacity': 72, 'load': 71.875, 'weights': [39.75, 32.0]},
 {'capacity': 72, 'load': 71.875, 'weights': [39.5, 32.25]},
 {'capacity': 72, 'load': 71.875, 'weights': [39.0, 32.75]},
 {'capacity': 72, 'load': 71.875, 'weights': [38.75, 33.0]},
 {'capacity': 72, 'load': 71.875, 'weights': [38.25, 33.5]},
 {'capacity': 72, 'load': 71.875, 'weights': [38.0, 33.75]},
 {'capacity': 72, 'load': 71.875, 'weights': [37.5, 34.25]},
 {'capacity': 72, 'load': 71.875, 'weights': [37.25, 34.5]},
 {'capacity': 72, 'load': 71.875, 'weights': [36.75, 35.0]},
 {'capacity': 72, 'load': 71.875, 'weights': [36.5, 35.25]},
 {'capacity': 54, 'load': 36.0, 'weights': [36.0]}]
"""