0-1 Knapsack problem dynamic programming

01knapsack.cpp

#include<stdio.h>

// A utility function that returns maximum of two integers
int max(int a, int b) { return (a > b)? a : b; }

// Returns the maximum value that can be put in a knapsack of capacity W
int knapsack(int val[], int weight[],int w,int n)
{
    if(n==0 || w==0 ) return 0;
    
    if(weight[n-1]>w)
        return knapsack(val,weight,w,n-1);
    else
        return max(val[n-1]+knapsack(val,weight,w-weight[n-1],n-1),   
        knapsack(val,weight,w,n-1) ); 
  

}
// Driver program to test above function
int main()
{
	int val[] = {60, 100, 120};
	int wt[] = {10, 20, 30};
	int W = 50;
	int n = sizeof(val)/sizeof(val[0]);
	printf("%d", knapsack(val,wt,W,n));
	return 0;
}

knapsack.py

def knapSack(W , wt , val , n):

	# Base Case
	if n == 0 or W == 0 :
		return 0

	# If weight of the nth item is more than Knapsack of capacity
	# W, then this item cannot be included in the optimal solution
	if (wt[n-1] > W):
		return knapSack(W , wt , val , n-1)

	# return the maximum of two cases:
	# (1) nth item included
	# (2) not included
	else:
		return max(val[n-1] + knapSack(W-wt[n-1] , wt , val , n-1),
				knapSack(W , wt , val , n-1))

# end of function knapSack

# To test above function
val = [60, 100, 120]
wt = [10, 20, 30]
W = 50
n = len(val)
print knapSack(W , wt , val , n)