The bin packer is a lab exam exercise from the 2006/2007 year. The question sheet can be found here.
On this page, I will build up the solution gradually. However, you can also see the full solution.
Task 1: findContainer()
The first task is to build a function to find a locate the the proper container to house a particular item. The specification for the function is clearly given in the description of task 1. Our first job should be to encode this specification as a function declaration:
def findContainer(listofcontainers, itemweight):
return -1
I've included a return -1 line, because I know I'll need this somewhere, to put in when there are no available containers. In an exam, just this declaration would give you a few marks - make sure you know how to build them!
Next, insert a plan for your code, written in comments:
def findContainer(listofcontainers, itemweight):
# iterate over containers
# if this container can accommodate
# return it
# if no container can accommodate, return -1
return -1
The thing to watch out for here is that although we check which container is appropriate by looking at weights in each container (the items in the list), we return the *index* - which container we need, which will be a position in the list.
Adding code for the iteration:
def findContainerOld(listofcontainers, itemweight):
# iterate over containers
for index in range(len(listofcontainers)):
# container is the weight inside this container
container = listofcontainers[index]
# if this container can accommodate
# return it
# if no container can accommodate, return -1
return -1
Note how the code fits around the comment plan. Finally, adding in the conditional to check when the container can accommodate the new weight:
def findContainer(listofcontainers, itemweight):
# iterate over containers
for index in range(len(listofcontainers)):
# container is the weight inside this container
container = listofcontainers[index]
# if this container can accommodate
if container + itemweight <= 20:
# return it
return index
# if no container can accommodate
return -1
Try some test cases to make sure it is working…
Task 2: using findContainer() as part of a solution
Again, start with a comment plan:
# get number from user
# keep going until a zero
# find where to file this
# file it
# if filepos is a position, just file
# otherwise, make a new container
The code to get numbers is fairly standard and we've used it a few times before:
# get number from user
innumber = input()
# keep going until a zero
while innumber != 0:
# find where to file this
# file it
# if filepos is a position, just file
# otherwise, make a new container
# get another number
innumber = input()
Add the code to call our previous function. This also shows us that we need a list of containers declared at the start, so we'd better declare that.
# empty list of containers
loc = [0]
# get number from user
innumber = input()
# keep going until a zero
while innumber != 0:
# find where to file this
filepos = findContainer(loc, innumber)
# file it
# if filepos is a position, just file
# otherwise, make a new container
# get another number
innumber = input()
Now add the code to cope with filing the number:
# empty list of containers
loc = [0]
# get number from user
innumber = input()
# keep going until a zero
while innumber != 0:
# find where to file this
filepos = findContainer(loc, innumber)
# file it
# if filepos is a position, just file
if filepos >= 0:
loc[filepos] = loc[filepos] + innumber
# otherwise, make a new container
else:
loc = loc + [ innumber ]
# get another number
innumber = input()
Finally, add code to count the number of items we've seen, and report them as we go. The output format is according to the specification in the question.
# how many items have we seen
counter = 1
# empty list of containers
loc = [0]
# get number from user
innumber = input()
# keep going until a zero
while innumber != 0:
# find where to file this
filepos = findContainer(loc, innumber)
# file it
# if filepos is a position, just file
if filepos > 0:
loc[filepos] = loc[filepos] + innumber
# Note we print the container index + 1, because containers are listed
# as being index from 1
print "Item", counter, "Weight", innumber, "Container", filepos + 1
# otherwise, make a new container
else:
loc = loc + [ innumber ]
print "Item", counter, "Weight", innumber, "Container", len(loc)
# get another number
innumber = input()
counter = counter + 1
Task 3: the new filing algorithm
This task asks you to implement a more sophisticated packing algorithm - selecting the bin which is the most full. Here is the code:
def findContainer(listofcontainers, itemweight):
# initialise best container
bestcontainer = -1
bestcontainerfullness = 0
# find the fullest container
# iterate over the containers
for index in range(len(listofcontainers)):
container = listofcontainers[index]
fullness = container + itemweight
# if this one is a better fit than the current, replace
if fullness <= 20 and fullness > bestcontainerfullness:
bestcontainer = index + 1
bestcontainerfullness = container + itemweight
return bestcontainer
Perhaps the most difficult issue in this algorithm is the separation between the weights in each container and the index into the container list: we have to make sure we store both.
- When the algorithm begins, the bestcontainer so far is -1 - this means that if the loop fails to find a container, it will return a -1 to say that no container was found.
- To begin with, the best "fullness" of container is 0. Any container fullness will be better than this, so as soon as we find a container which has enough capacity, it will be chosen.
- The conditional in the loop checks to see whether the current container has enough space for the new item, and if filing into this container would create a more full container than the others we've currently seen.
Full solution
Note how the solution is modular - we can easily swap in a different function for findContainer().
def findContainerOld(listofcontainers, itemweight):
# iterate over containers
for index in range(len(listofcontainers)):
# container is the weight inside this container
container = listofcontainers[index]
# if this container can accommodate
if container + itemweight <= 20:
# return it
return index
# if no container can accommodate
return -1
def findContainer(listofcontainers, itemweight):
# initialise best container
bestcontainer = -1
bestcontainerfullness = 0
# find the fullest container
# iterate over the containers
for index in range(len(listofcontainers)):
container = listofcontainers[index]
fullness = container + itemweight
# if this one is a better fit than the current, replace
if fullness <= 20 and fullness > bestcontainerfullness:
bestcontainer = index + 1
bestcontainerfullness = container + itemweight
return bestcontainer
# how many items have we seen
counter = 1
# empty list of containers
loc = [0]
# get number from user
innumber = input()
# keep going until a zero
while innumber != 0:
# find where to file this
filepos = findContainer(loc, innumber)
# file it
# if filepos is a position, just file
if filepos > 0:
loc[filepos] = loc[filepos] + innumber
# Note we print the container index + 1, because containers are listed
# as being index from 1
print "Item", counter, "Weight", innumber, "Container", filepos + 1
# otherwise, make a new container
else:
loc = loc + [ innumber ]
print "Item", counter, "Weight", innumber, "Container", len(loc)
# get another number
innumber = input()
counter = counter + 1
