Dynamic programming solution to knapsack problem in python.

knapsack.py

#For simulations
import random 

class Item(object):
	def __init__(self, value=0, weight=0):
		self.value = value
		self.weight = weight

	def __repr__(self):
		return "({value}, {weight})".format(**self.__dict__)

def knap_table(items, capacity):
	"""
	Construct optimal substructure table
	"""
	items = [Item()] + items
	item_length = len(items)
	table = [[0]*(capacity+1) for i in xrange(item_length)]

	for i in xrange(1, item_length):
		item = items[i]
		for w in xrange(0, capacity + 1):
			if (w - item.weight) < 0:
				table[i][w] = table[i-1][w]
			else:
				with_current = table[i-1][w-item.weight] + item.value
				without_current = table[i-1][w]
				table[i][w] = max(with_current, without_current)

	return (items, table)

def knap_items(items, capacity, table):
	"""
	Reconstruct optimal solution from the table
	"""
	knap_items = []

	current_weight = capacity
	for i in xrange(len(items)-1, 0, -1):
		if current_weight <= 0:
			break
		item = items[i]
		added_weight = current_weight-item.weight
		if added_weight < 0:
			continue

		if table[i][current_weight] - table[i-1][added_weight] == item.value:
			current_weight -= item.weight
			knap_items.append(item)

	return knap_items		

def knap(items, capacity):
	"""
	Public API to solve the knapsack problem. 
	Returns tuple with a list of selected items and also the 
	efficiency - (sum(weights) / capacity)
	"""
	items, table = knap_table(items, capacity)
	items = knap_items(items, capacity, table)
	return (items, sum(map(lambda x:x.weight, items))*1.0/capacity)

def run():
	"""
	Run some random simulations.
	"""
	value_range = 100
	weight_range = 100
	item_count = 100
	items = [Item(value=random.randint(0, 100), weight=random.randint(0, 100)) 
		for i in xrange(item_count)]

	for capacity in xrange(1, weight_range+1):
		print capacity, knap(items, capacity)
	

if __name__ == '__main__':
	run()