0 1 Knapsack

Problem Link: https://practice.geeksforgeeks.org/problems/0-1-knapsack-problem0945/1

class Solution:
    
    #Function to return max value that can be put in knapsack of capacity W.
    def knapSack(self,W, wt, val, n):
        
        dp=[[0 for i in range(W+1)] for j in range(n+1)]
        for i in range(n+1):
            for j in range(W+1):
                if(i==0 or j==0):
                    dp[i][j]=0
                else:
                    if(wt[i-1]<=j):
                        inc=val[i-1]+dp[i-1][j-wt[i-1]]
                        exc=dp[i-1][j]
                        dp[i][j]=max(inc,exc)
                    else:
                        exc=dp[i-1][j]
                        dp[i][j]=exc
        
        return dp[n][W]