Knapsack with DP

knapsack_dp.py

#!/usr/bin/env python

values = [5, 10, 15]
weights = [1, 2, 3]
W = 5
n = len(values)
 
S = [[None for _ in range(W + 1)] for _ in range(n + 1)]

def knapsack(w, v, W, i):
  if i == 0 or W == 0:
     # trivial case
     return 0
  if S[i][W] is not None:
     # this case has already been seen
     return S[i][W]
  
  if w[i-1] > W:
     # the item doesnt fit!
     S[i][W] = knapsack(w, v, W, i-1)
     return S[i][W]
  else:
     with_item = v[i-1] + knapsack(w, v, W - w[i-1], i-1)
     without_item = knapsack(w, v, W, i-1)
     S[i][W] = max(with_item, without_item) 
     return S[i][W]

print("Maximum value is", knapsack(weights, values, W, n))
print(S)