knapsack2.py

# 0-1 knapsack problem dynamic program
# David Eppstein, ICS, UCI, 2/22/2002

# each item to be packed is represented as a set of triples (size,value,name)
def itemSize(item): return item[0]
def itemValue(item): return item[1]
def itemName(item): return item[2]

# example used in lecture
exampleItems = [(3,3,'A'),
		(4,1,'B'),
		(8,3,'C'),
		(10,4,'D'),
		(15,3,'E'),
		(20,6,'F')]

exampleSizeLimit = 32

# inefficient recursive algorithm
# returns optimal value for given
#
# note items[-1] is the last item, items[:-1] is all but the last item
#
def pack1(items,sizeLimit):
	if len(items) == 0:
		return 0
	elif itemSize(items[-1]) > sizeLimit:
		return pack(items[:-1],sizeLimit)
	else:
		return max(pack(items[:-1],sizeLimit),
			   pack(items[:-1],sizeLimit-itemSize(items[-1])) +
				itemValue(items[-1]))

# refactor so all params are integers
#
def pack2(items,sizeLimit):
	def recurse(nItems,lim):
		if nItems == 0:
			return 0
		elif itemSize(items[nItems-1]) > lim:
			return recurse(nItems-1,lim)
		else:
			return max(recurse(nItems-1,lim),
				   recurse(nItems-1,lim-itemSize(items[nItems-1])) +
					itemValue(items[nItems-1]))
	return recurse(len(items),sizeLimit)

# memoize
#
# Unlike previous class examples, I'm going to use a Python dictionary
# rather than a list of lists, because it's similarly efficient but can
# handle double indexing better.  Also that way I can use the has_key method
# instead of having to initialize each entry with a flag value.
#
# The difference in actual syntax is dictionary[item1,item2] instead of
# listoflists[item1][item2], and an empty dictionary is {} instead of [].
# The extra pair of parens in has_key is also important.
#
def pack3(items,sizeLimit):
	P = {}

	def recurse(nItems,lim):
		if not P.has_key((nItems,lim)):
			if nItems == 0:
				P[nItems,lim] = 0
			elif itemSize(items[nItems-1]) > lim:
				P[nItems,lim] = recurse(nItems-1,lim)
			else:
				P[nItems,lim] = max(recurse(nItems-1,lim),
				    recurse(nItems-1,lim-itemSize(items[nItems-1])) +
					itemValue(items[nItems-1]))
		return P[nItems,lim]

	return recurse(len(items),sizeLimit)

# iterate
# 
# At this step we have to think about how to order the nested loops over
# the two indices nItems and lim.  Each recursive call involves nItems-1,
# so the natural choice is to make the outer loop be over values of nItems.
# The ordering in the inner loop is not so important.
#
# The recursive function definition and has_key lines have been replaced
# by a nested pair of loops.  All recursive calls have been replaced
# by dictionary lookups.
#
def pack4(items,sizeLimit):
	P = {}
	for nItems in range(len(items)+1):
		for lim in range(sizeLimit+1):
			if nItems == 0:
				P[nItems,lim] = 0
			elif itemSize(items[nItems-1]) > lim:
				P[nItems,lim] = P[nItems-1,lim]
			else:
				P[nItems,lim] = max(P[nItems-1,lim],
				    P[nItems-1,lim-itemSize(items[nItems-1])] +
					itemValue(items[nItems-1]))
	return P[len(items),sizeLimit]
	
# backtrack through the matrix of solution values to find actual solution
#
# Like the LCS problem, and unlike the matrix chain problem, we only need
# to backtrack along a single path in the matrix, so we can do it with a
# while loop instead of a recursion.  We add each item to the end of a
# list L, then reverse L to match the input order -- it would work to add
# each item to the beginning of L but that's much less efficient in Python.
#
def pack5(items,sizeLimit):
	P = {}
	for nItems in range(len(items)+1):
		for lim in range(sizeLimit+1):
			if nItems == 0:
				P[nItems,lim] = 0
			elif itemSize(items[nItems-1]) > lim:
				P[nItems,lim] = P[nItems-1,lim]
			else:
				P[nItems,lim] = max(P[nItems-1,lim],
				    P[nItems-1,lim-itemSize(items[nItems-1])] +
					itemValue(items[nItems-1]))

	L = []
	nItems = len(items)
	lim = sizeLimit
	while nItems > 0:
		if P[nItems,lim] == P[nItems-1,lim]:
			nItems -= 1
		else:
			nItems -= 1
			L.append(itemName(items[nItems]))
			lim -= itemSize(items[nItems])

	L.reverse()
	return L

# run the example
# output = ['A', 'C', 'F']
print pack5(exampleItems,exampleSizeLimit)