fork download 
  1.  
  2. from collections import namedtuple
  3. Item = namedtuple('Item', 'weight cost')
  4.  
  5. def knapsack_costs(items, weight_limit):
  6. 	current_col = [0] * (weight_limit + 1)
  7. 	for i in xrange(1, len(items) + 1):
  8. 		item = items[i - 1]
  9. 		for w in xrange(weight_limit, 0, -1):
  10. 			current_col[w] = max(current_col[w], current_col[w - 1])
  11. 			if w >= item.weight:
  12. 				current_col[w] = max(
  13. 					current_col[w],
  14. 					current_col[w - item.weight] + item.cost
  15. 				)
  16. 	return current_col
  17.  
  18. def knapsack(items, weight_limit):
  19. 	if not items or not weight_limit:
  20. 		return []
  21. 	if len(items) == 1:
  22. 		return [items[0]] if items[0].weight <= weight_limit else []
  23. 	m = len(items) / 2
  24. 	items_left = items[:m]
  25. 	items_right = items[m:]
  26. 	costs_left = knapsack_costs(items_left, weight_limit)
  27. 	costs_right = knapsack_costs(items_right, weight_limit)
  28. 	best_i = 0
  29. 	best_cost = 0
  30. 	for i in xrange(weight_limit + 1):
  31. 		cur_cost = costs_left[i] + costs_right[-1 - i]
  32. 		if cur_cost > best_cost:
  33. 			best_i = i
  34. 			best_cost = cur_cost
  35. 	return knapsack(items_left, best_i) + knapsack(items_right, weight_limit - best_i)
  36.  
  37.  
  38. print knapsack([Item(1,100), Item(2, 200), Item(5, 3000)], 7)
Success #stdin #stdout 0s 23688KB
comments ()
stdin 
Standard input is empty
stdout 
[Item(weight=2, cost=200), Item(weight=5, cost=3000)]
https://ideone.com/abUEBD
language:
Python (cpython 2.7.16)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!