Thanks Kent
Your program does what i wanted to accomplish. But i dont really know why, and that disturbs me.
I guess its the class that confuses me. Could you or sombody else on this list help me out by putting some words on what is happening in this program, and in which order things are done?
OK, I'll try.
First I define a class to represent a bin of items. What are the characteristics of a bin? A bin contains the actual items, which are represented as a list. But a bin also has a sum, the total of its items. Keeping a running sum as a separate attribute lets me avoid computing the sums each time I want to know what it is.
This is a pretty good example of a simple class, for those listening in. A Bin has a state - its list of items and its sum - and two simple behaviors - adding an item and creating a string representation.
Let's try one out:
>>> b=Bin() >>> print b Bin(sum=0, items=[]) >>> b.append(1) >>> print b Bin(sum=1, items=[1]) >>> b.append(10) >>> print b Bin(sum=11, items=[1, 10])
I can access the sum and the item list directly: >>> b.sum 11 >>> b.items [1, 10]
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))
Now define a function to do the actual bin packing. It takes two arguments - a list of the values to be packed, and the maximum sum allowed in a bin.
def pack(values, maxValue):
The algorithm works best with a sorted list. If your list is already sorted, you don't need this line. If you are using a version of Python older than 2.4, you need to write this differently.
#values = sorted(values, reverse=True)
This is a list of Bins. Initially it is empty.
bins = []
Now start putting items into bins.
for item in values:
Go through the Bins in order, looking for one that can hold the current item
# Try to fit item into a bin for bin in bins: if bin.sum + item <= maxValue:
We found a Bin that has room, add the item to the bin and break out of the bin search loop
#print 'Adding', item, 'to', bin bin.append(item) break
This code will only be run if the for loop ran to completion - if it did NOT terminate with a break. That only happens if we didn't find a Bin with room for the item. So, let's make a new bin.
else: # item didn't fit into any bin, start a new bin #print 'Making new bin for', item
Make a new bin
bin = Bin()
Add the item to the bin
bin.append(item)
Add the bin to the list of bins
bins.append(bin)
When we get here all the items have been placed in bins, we are done.
return bins
This is test code
if __name__ == '__main__': import random
Here is a function that packs a list into Bins and prints out the result. It is handy for testing.
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
This is a simple test case
aList = [10,9,8,7,6,5,4,3,2,1] packAndShow(aList, 11)
Here is a bigger test case using a list of random numbers
aList = [ random.randint(1, 11) for i in range(100) ] packAndShow(aList, 11)
HTH, Kent
_______________________________________________ Tutor maillist - Tutor@python.org http://mail.python.org/mailman/listinfo/tutor
