0/1 Knapsack

'''
Knanpsack 0/1
if enough space in knapsack remaining, then either you can take it(& add it's profit) or avoid it, else you will have to avoid
and consider the maximum profit out of these cases.
base case:
1)When no space in knapsack, so no items can be pushed, so no profit, return 0
2)When no elements are there, so no profit can be made, return 0
'''
def fun(w,n,val,wt,dp):
    if w<=0:
        return 0
    if n<0:
        return 0
    if dp[w][n]!=-1:
        return dp[w][n]
    take=0
    if w>=wt[n]:
        take=val[n]+fun(w-wt[n],n-1,val,wt,dp) #take profit due to including the item
    not_take=fun(w,n-1,val,wt,dp)
    dp[w][n]=max(take,not_take)
    return dp[w][n]

class Solution:
    def knapsack(self, W, val, wt):
        dp=[[-1]*len(wt) for _ in range(W+1)]
        return fun(W,len(wt)-1,val,wt,dp)