zjplab
2/15/2017 - 1:26 PM

## 0-1 Knapsack problem dynamic programming

0-1 Knapsack problem dynamic programming

``````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)
``````
``````#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;
}``````