Рюкзак 0/1

1function knapsack(items: Array<[w: number, v: number]>, cap: number): number {
2  const n = items.length
3  // d[i][c] — максимум ценности из первых i предметов при вместимости c
4  const d: number[][] = Array.from({ length: n + 1 }, () =>
5    new Array(cap + 1).fill(0),
6  )
7 
8  for (let i = 1; i <= n; i++) {
9    const [w, v] = items[i - 1]!
10    for (let c = 0; c <= cap; c++) {
11      d[i][c] = d[i - 1][c] // не берём предмет i
12      if (w <= c && d[i - 1][c - w] + v > d[i][c]) {
13        d[i][c] = d[i - 1][c - w] + v // берём
14      }
15    }
16  }
17 
18  return d[n][cap]
19}