Created
March 25, 2017 19:49
-
-
Save MohamedFawzy/f75af533c69aaa03fca112787e23a735 to your computer and use it in GitHub Desktop.
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
#Dynamic Programming based Python Program for 0-1 Knapsack problem | |
# Returns the maximum value that can be put in a knapsack of capacity W | |
def knapSack(W, wt, val, n): | |
K = [[0 for x in range(W+1)] for x in range(n+1)] | |
#build table k[][] in bottom up manner | |
for i in range(n+1): | |
for w in range(W+1): | |
if i==0 or w==0: | |
K[i][w]=0 | |
elif wt[i-1] <= w: | |
K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]], K[i-1][w]) | |
else: | |
K[i][w] = K[i-1][w] | |
return K[n][W] | |
val = [100, 40, 70] | |
wt = [4,2,3] | |
W = 5 | |
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