Created
December 3, 2015 02:54
-
-
Save agfor/42a98ec4d8f3bb0a2e93 to your computer and use it in GitHub Desktop.
Brute force multiple subset sum solution
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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]}] | |
""" |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment