pythonprogram/Knapsack_problem.py at master · seeditsolution/pythonprogram · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
# A Dynamic Programming based Python
# Program for 0-1 Knapsack problem
# Returns the maximum value that can
# be put in a knapsack of capacity W
defknapSack(W, wt, val, n):
K= [[0forxinrange(W+1)] forxinrange(n+1)]

# Build table K[][] in bottom up manner
foriinrange(n+1):
forwinrange(W+1):
ifi==0orw==0:
K[i][w] =0
elifwt[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]

returnK[n][W]

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

# This code is contributed by Vanasetty Rohit