1function knapsack01(items, capacity) {
2 const n = items.length;
3 const dp = Array(n + 1).fill(0).map(() => Array(capacity + 1).fill(0));
4
5 for (let i = 1; i <= n; i++) {
6 const { weight, value } = items[i - 1];
7 for (let w = 0; w <= capacity; w++) {
8 if (weight > w) {
9 dp[i][w] = dp[i - 1][w]; // Item too heavy
10 } else {
11 const exclude = dp[i - 1][w];
12 const include = value + dp[i - 1][w - weight];
13 dp[i][w] = Math.max(exclude, include);
14 }
15 }
16 }
17
18 // Traceback optimal solution
19 let w = capacity, selected = [];
20 for (let i = n; i > 0 && w > 0; i--) {
21 if (dp[i][w] !== dp[i - 1][w]) {
22 selected.push(items[i - 1]);
23 w -= items[i - 1].weight;
24 }
25 }
26 return { maxValue: dp[n][capacity], selected };
27}