Dynamic Programming

Examples

• 0

  Unbounded Knapsack Problem

  edit move example delete share

  0

  The Unbounded Knapsack Problem is a problem which given a set of items, each with a weight, a value and infinite copies, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible.

  Python(2.7.11) Example:

  Implementation:

  def unbounded_knapsack(w, v, c): # weight, value and capactiy
      m = [0]
      for r in range(1, c+1):
          val = m[r-1]
          for i, wi in enumerate(w):
              if wi > r:
                  continue
              val = max(val, v[i] + m[r-wi])
          m.append(val)
      return m[c] # return the maximum value can be achieved
  

  The complexity of that implementation is O(nC), which n is number of items.

  Test:

  w = [2, 3, 4, 5, 6]
  v = [2, 4, 6, 8, 9]
  
  print unbounded_knapsack(w, v, 13)
  

  Output:

  20
  

  That means the maximum value can be achieved is 20, which is achieved by choosing (5, 8), (5, 8) and (3, 4).

  created Jul 22 at 12:44