fork(8) download
copy 
  1. from itertools import product, izip
  2. from collections import namedtuple
  3.  
  4. Bounty = namedtuple('Bounty', 'name value weight volume')
  5.  
  6. # "namedtuple" is only available in Python 2.6+; for earlier versions use this instead:
  7. # class Bounty:
  8. #     def __init__(self, name, value, weight, volume):
  9. #         self.name = name
  10. #         self.value = value
  11. #         self.weight = weight
  12. #         self.volume = volume
  13.  
  14. sack =   Bounty('sack',       0, 25, 42)
  15.  
  16. items = [Bounty('panacea', 3000,   3,  25),
  17.          Bounty('ichor',   1800,   2,  15),
  18.          Bounty('gold',    2500,  20,   2)]
  19.  
  20.  
  21. def tot_value(items_count, items, sack):
  22.     """
  23.     Given the count of each item in the sack return -1 if they can't be carried or their total value.
  24.  
  25.     (also return the negative of the weight and the volume so taking the max of a series of return
  26.     values will minimise the weight if values tie, and minimise the volume if values and weights tie).
  27.     """
  28.     weight = sum(n * item.weight for n, item in izip(items_count, items))
  29.     volume = sum(n * item.volume for n, item in izip(items_count, items))
  30.     if weight <= sack.weight and volume <= sack.volume:
  31.         return sum(n * item.value for n, item in izip(items_count, items)), -weight, -volume
  32.     else:
  33.         return -1, 0, 0
  34.  
  35.  
  36. def knapsack_dp(items, sack):
  37.     if(sum(item.weight for item in items) <= sack.weight
  38.         and sum(item.volume for item in items) <= sack.volume):
  39.         return [1] * len(items)
  40.  
  41.     table = [[0] * (sack.volume + 1) for i in xrange(sack.weight + 1)]
  42.  
  43.     for item in items:
  44.         for w in reversed(xrange(sack.weight + 1)):
  45.             for v in reversed(xrange(sack.volume + 1)):
  46.                 if w >= item.weight and v >= item.volume:
  47.                     table[w][v] = max(table[w][v], table[w - item.weight][v - item.volume] + item.value)
  48.  
  49.     # Backtrack through matrix to re-construct optimum:
  50.     result = [0] * len(items)
  51.     w = sack.weight
  52.     v = sack.volume
  53.     print table[w][v]
  54.     while table[w][v]:
  55.         # Find the last item that was added:
  56.         aux = [table[w-item.weight][v-item.volume] + item.value for item in items]
  57.         i = aux.index(table[w][v])
  58.  
  59.         # Record it in the result, and remove it:
  60.         result[i] = 1
  61.         w -= items[i].weight
  62.         v -= items[i].volume
  63.  
  64.     return result
  65.  
  66.  
  67. max_items = knapsack_dp(items, sack)
  68. max_value, max_weight, max_volume = tot_value(max_items, items, sack)
  69. max_weight = -max_weight
  70. max_volume = -max_volume
  71.  
  72. print "The maximum value achievable (by exhaustive search) is %g." % max_value
  73. item_names = ", ".join(item.name for item in items)
  74. print "  The number of %s items to achieve this is: %s, respectively." % (item_names, max_items)
  75. print "  The weight to carry is %.3g, and the volume used is %.3g." % (max_weight, max_volume)
Success #stdin #stdout 0.02s 9128KB
comments ()
stdin
copy 
Standard input is empty
stdout
copy 
The maximum value achievable (by exhaustive search) is 7300.
  The number of panacea, ichor, gold items to achieve this is: [1, 1, 1], respectively.
  The weight to carry is 25, and the volume used is 42.
https://ideone.com/FgrHzZ
language:
Python (cpython 2.7.16)
created:
9 years ago
visibility:
secret

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!