items × capacity, где ячейка dp[i][w] хранит лучшую стоимость при использовании первых i предметов и вместимости w. Переход: максимум из «не брать предмет i» и «взять его, если помещается». В конце восстанавливаем состав решения, двигаясь по таблице вверх.Время – O(n·W), память – O(n·W) (или O(W) с одномерной оптимизацией без восстановления решения).
1type Item = { name: string; weight: number; value: number };23/**4 * Классический 0/1 knapsack с восстановлением набора предметов.5 * dp[i][w] – лучшая стоимость при использовании первых i предметов и вместимости w.6 * keep[i][w] – включён ли предмет i в оптимум для этой ячейки.7 */8function knapsack(items: Item[], capacity: number): { value: number; taken: string[] } {9 const n = items.length;10 const dp: number[][] = Array.from({ length: n + 1 }, () => Array(capacity + 1).fill(0));11 const keep: boolean[][] = Array.from({ length: n + 1 }, () => Array(capacity + 1).fill(false));1213 for (let i = 1; i <= n; i++) {14 const { weight, value } = items[i - 1];15 for (let w = 0; w <= capacity; w++) {16 // не берём i-й17 let best = dp[i - 1][w];18 // пробуем взять i-й, если помещается19 if (weight <= w) {20 const candidate = dp[i - 1][w - weight] + value;21 if (candidate > best) {22 best = candidate;23 keep[i][w] = true;24 }25 }26 dp[i][w] = best;27 }28 }2930 // восстановление ответа31 const taken: string[] = [];32 let w = capacity;33 for (let i = n; i >= 1; i--) {34 if (keep[i][w]) {35 taken.push(items[i - 1].name);36 w -= items[i - 1].weight;37 }38 }39 taken.reverse();40 return { value: dp[n][capacity], taken };41}4243/*** Пример (по мотивам «Грокаем алгоритмы») ***/44const items: Item[] = [45 { name: 'guitar', weight: 1, value: 1500 },46 { name: 'stereo', weight: 4, value: 3000 },47 { name: 'laptop', weight: 3, value: 2000 },48];4950const { value, taken } = knapsack(items, 4);51console.log('best value:', value); // -> 350052console.log('taken:', taken.join(', ')); // -> guitar, laptop53