0/1 Knapsack Problem
Maximize total value in a knapsack of capacity W.
Enter inputs and click Run
Status: Ready
Speed
Algorithm Logic
1function knapsack(W, wt, val, n):
2 dp = table(n+1, W+1, 0)
3
4 for i from 1 to n:
5 for w from 0 to W:
6 if wt[i-1] <= w:
7 dp[i][w] = max(
8 val[i-1] + dp[i-1][w-wt[i-1]],
9 dp[i-1][w]
10 )
11 else:
12 dp[i][w] = dp[i-1][w]
13
14 return dp[n][W]