Created
February 15, 2017 13:26
-
-
Save zjplab/f92d7c73e2a326115343627e49c1fd94 to your computer and use it in GitHub Desktop.
0-1 Knapsack problem dynamic programming
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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; | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment