Loading…
Loading…
Pack the most valuable subset within a weight limit. Each cell asks one question: skip this item, or take it?
Items: w2/v3 · w3/v4 · w4/v5 · w5/v8
Row ∅ means "no items offered": whatever the capacity, the best value is 0. Every other cell will be built from the row above it.
1int knapsack(int[] wt, int[] val, int W) {2 int n = wt.length;3 int[][] dp = new int[n + 1][W + 1]; // row 0 stays all zeros4 for (int i = 1; i <= n; i++)5 for (int w = 0; w <= W; w++) {6 dp[i][w] = dp[i-1][w]; // skip item i7 if (wt[i-1] <= w)8 dp[i][w] = Math.max(dp[i][w],9 val[i-1] + dp[i-1][w - wt[i-1]]); // take it — add its value10 }11 return dp[n][W];12}