Created
November 4, 2016 07:30
-
-
Save aljiwala/3b9f33f4f5367b853c63a82b77f9da58 to your computer and use it in GitHub Desktop.
Bin Packing Algorithm
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
''' Partition a list into sublists whose sums don't exceed a maximum | |
using a First Fit Decreasing algorithm. | |
''' | |
class Bin(object): | |
''' Container for items that keeps a running sum ''' | |
def __init__(self): | |
self.items = [] | |
self.sum = 0 | |
def append(self, item): | |
self.items.append(item) | |
self.sum += item | |
def __str__(self): | |
''' Printable representation ''' | |
return 'Bin(sum=%d, items=%s)' % (self.sum, str(self.items)) | |
def pack(values, maxValue): | |
values = sorted(values, reverse=True) | |
bins = [] | |
for item in values: | |
# Try to fit item into a bin | |
for bin in bins: | |
if bin.sum + item <= maxValue: | |
#print 'Adding', item, 'to', bin | |
bin.append(item) | |
break | |
else: | |
# item didn't fit into any bin, start a new bin | |
#print 'Making new bin for', item | |
bin = Bin() | |
bin.append(item) | |
bins.append(bin) | |
return bins | |
if __name__ == '__main__': | |
import random | |
def packAndShow(aList, maxValue): | |
''' Pack a list into bins and show the result ''' | |
print 'List with sum', sum(aList), 'requires at least', (sum(aList)+maxValue-1)/maxValue, 'bins' | |
bins = pack(aList, maxValue) | |
print 'Solution using', len(bins), 'bins:' | |
for bin in bins: | |
print bin | |
aList = [10,9,8,7,6,5,4,3,2,1] | |
packAndShow(aList, 11) | |
aList = [ random.randint(1, 11) for i in range(100) ] | |
packAndShow(aList, 11) | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment