"""
 knapsack.py

 The classic knapsack problem.

 Find the most value that will fit 

"""

n = 4                             # number of items = n
capacity = 8                      # maximum weight  = w
value = [15, 10, 9, 5]
weight = [1, 5, 3, 4]

# approach 1: brute force
# O(2**n) 
# (0,1) version of problem i.e. zero or one of each item.

"Do in class"

# approach 2: dynamic programming
# O(n*w)
#   answer[i, w] = i items, max value up to capacity=w
#   edge conditions :    answer[0,w] no items = answer[i,0] no weight = 0
#   recursion relation : answer[w,i] = max (v[j] + answer[w,i-1])
#                                      for j not yet in bag & total weight < w

"Do in class"