0-1 Knapsack Problem in Python

In the 0-1 Knapsack problem we have a knapsack that will hold a specific weight and we have a series of objects to place in it. Each object has a weight and a value. Our goal is best utilize the space in the knapsack by maximizing the value of the objects placed in it. This is the classic 0-1 knapsack problem. It's called the 0-1 knapsack problem because you can not place part of an object in the knapsack for part of the profit. You must place all of it or none. There are many other Knapsack problems as well.

The formal definition of this Knapsack problem and other scan be found here in this paper by David Pisinger.

So for example, If we had two items. One that weighs 1 pound that we could sell for 1 dollar. And one that weighs 2 pounds that we could sell for 3 dollars. If our knapsack could hold 1 pound we would only be able to place in it the first item and claim 1 dollar. For a 2 pound knapsack we could hold the second item and claim 3 dollars. And we if had a 3 or more pound knapsack we would be able to carry both items and claim 4 dollars.

While this example is easy to understand as the number of items increases the problem becomes more and more difficult to solve. Dynamic Programming can be used to solve this problem. In order to solve the problem we must first observe that the maximum profit for a knapsack of size W is equal to the greater of a knapsack of size W-1 or a knapsack  with a valid item in plus the max profit of a knapsack of size W-w[i] where w[i] is the weight of said valid item.

If this seems a bit confusing you are not alone. In the first example, a knapsack of size 3 is equal to the grater profit of a knapsack of size 2, which we know is 3, or adding the valid second item with a weight of 2 plus the profit of the know knapsack that holds any left over weight. In this case the a 3 pound knapsack with a two pound item there is a remainder of 1 pound. So the choice is the knapsack of size 2 with a profit of 3 or a knapsack with the second item plus a knapsack of size 1 with a profit of 4. Obviously we would choose the latter with a profit of 4.

These rules show that we have a direct correlation between knapsack of size W and all of the knapsacks smaller than size W. So, if we know all of the knapsacks that are smaller than W we can easily figure out the maximum profit of a knapsack of size W. This is exactly what is accomplished by the dynamic programming solution. First we start with the smallest knapsack size and look at the profit we can get by adding each item individually to it as we increase the knapsack size. As shown here:
# v = list of item values or profit
# w = list of item weight or cost
# W = max weight or max cost for the knapsack
def zeroOneKnapsack(v, w, W):
	# c is the cost matrix
	c = []
	n = len(v)
	c = zeros(n,W+1)
	for i in range(0,n):
		#for ever possible weight
		for j in range(0,W+1):		
	                #can we add this item to this?
			if (w[i] > j):
				c[i][j] = c[i-1][j]
			else:
				c[i][j] = max(c[i-1][j],v[i] +c[i-1][j-w[i]])
	return [c[n-1][W], getUsedItems(w,c)]

In the above code, first we create a N by W matrix where N is the size number of items and W is the maximum weight the knapsack can hold. When the code has completed with the above example items the cost matrix with rows correspoding to items and columns correspondig to weights for a knapsack of W=4 will look like this:

01111
01234

Cell c[i,j] of the matrix is the optimal profit for 0-i items of cost j. The answer to the question what is the maximum profit given these items for a 4 pound knapsack is located in the bottom right of the matrix.


In addition to just the maximum profit we might also like to know what items we were placed into the knapsack. The 0-1 knapsack problem assumes that we are simply going to place or omit a given item into the knapsack. So looking back at the cost matrix we can find out what items were selected.

If cell[i,j] is equal to cell[i-1,j] then item i was should not be in the bag. If they are not equal than it is in the bag. After we place that item in the bag we decase the avaiable weight corresponding to the item added and ask the same question again. Shown here:

# w = list of item weight or cost
# c = the cost matrix created by the dynamic programming solution
def getUsedItems(w,c):
    # item count
	i = len(c)-1
	currentW =  len(c[0])-1
	# set everything to not marked
	marked = []
	for i in range(i+1):
		marked.append(0)			
	while (i >= 0 and currentW >=0):
		if (i==0 and c[i][currentW] >0 )or c[i][currentW] != c[i-1][currentW]:
			marked[i] =1
			currentW = currentW-w[i]
		i = i-1
	return marked

The output of this is a list of each item that was included in the knapsack.

This code can be added to above to make a single functional script.

def zeros(rows,cols):
	row = []
	data = []
	for i in range(cols):
		row.append(0)
	for i in range(rows):
		data.append(row[:])
	return data
if (len(sys.argv)!=3):
	print "Usage knapsack.py weight1-profit1,weight2-profit2,... max weight"
	print "Example:"
	print "knapsack.py 1-2,2-5,3-10 12"
	quit()
 
items = sys.argv[1].split(',')
w = []
v = []
total =0
for item in items:
	nums = item.split('-')
	w.append(int(nums[0]))
	v.append(int(nums[1]))
 
maxCost = int(sys.argv[2])
answer = zeroOneKnapsack(v,w,maxCost)
print "if my knapsack can hold %d pounds, i can get %d profit." % (maxCost,answer[0])
print "\tby taking item(s): ",
for i in range(len(answer[1])):
	if (answer[1][i] != 0):
		print i+1,


ċ
knapsack.py
(3k)
Michael Knight,
Jan 28, 2009, 5:54 AM
Comments