from collections import namedtuple
Item = namedtuple('Item', 'weight cost')

def knapsack_costs(items, weight_limit):
	current_col = [0] * (weight_limit + 1)
	for i in xrange(1, len(items) + 1):
		item = items[i - 1]
		for w in xrange(weight_limit, 0, -1):
			current_col[w] = max(current_col[w], current_col[w - 1])
			if w >= item.weight:
				current_col[w] = max(
					current_col[w],
					current_col[w - item.weight] + item.cost
				)
	return current_col

def knapsack(items, weight_limit):
	if not items or not weight_limit:
		return []
	if len(items) == 1:
		return [items[0]] if items[0].weight <= weight_limit else []
	m = len(items) / 2
	items_left = items[:m]
	items_right = items[m:]
	costs_left = knapsack_costs(items_left, weight_limit)
	costs_right = knapsack_costs(items_right, weight_limit)
	best_i = 0
	best_cost = 0
	for i in xrange(weight_limit + 1):
		cur_cost = costs_left[i] + costs_right[-1 - i]
		if cur_cost > best_cost:
			best_i = i
			best_cost = cur_cost
	return knapsack(items_left, best_i) + knapsack(items_right, weight_limit - best_i)


print knapsack([Item(1,100), Item(2, 200), Item(5, 3000)], 7)