topDownKnapsack.py

def topDownKnapsack(wt,val,capacity):
    dp = [[0 for i in range(capacity+1)] for j in range(len(wt)+1)]
    for i in range(len(wt)+1):
        for j in range(capacity+1):
            if i == 0 or j == 0:
                dp[i][j] = 0
            elif wt[i-1] <= j:
                dp[i][j] = max(
                    val[i - 1] + dp[i - 1][j - wt[i - 1]],
                               dp[i - 1][j])      
            else:
                 dp[i][j] = dp[i - 1][j]
                      
    return dp[len(wt)][capacity]
  
def main():
  wt = [10,40,20,30]
  val = [60,40,100,120]
  capacity = 50
  topDownKnapsack(wt,val,capacity)

if __name__ == "__main__":
    main()