Back to Topics
Dynamic Programming
Solve complex problems by breaking them down into simpler subproblems and storing the results.
0/1 Knapsack
Practice Scenarios
No examples added yet.
You can add coding problem links here and check them off as you complete them.
Pseudocode Implementation
function knapsack(W, wt, val, n):
K = 2D array of size (n+1) x (W+1)
for i = 0 to n:
for w = 0 to W:
if i == 0 or w == 0:
K[i][w] = 0
else if 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]