Как решить задачу о рюкзаке 0/1 динамическим программированием?

`dp[w]` — максимальная ценность при вместимости `w`; для каждого предмета обновляем `dp[w] = max(dp[w], dp[w − weight] + value)`, перебирая `w` по убыванию. Время `O(n·W)`, память `O(W)`.

Рекуррентность

• Полная таблица: dp[i][w] = max(dp[i−1][w], dp[i−1][w − wᵢ] + vᵢ) — предмет i либо не берём, либо берём.
• Одномерная версия идёт по w сверху вниз, чтобы dp[w − weight] ещё относился к предыдущему предмету. Обход снизу вверх — частая ошибка: он позволяет взять предмет несколько раз, а это уже неограниченный рюкзак.

const knapsack = (items, cap) => {
  const dp = new Array(cap + 1).fill(0);
  for (const [weight, value] of items) {
    for (let w = cap; w >= weight; w--) {
      dp[w] = Math.max(dp[w], dp[w - weight] + value);
    }
  }
  return dp[cap];
};

knapsack([[10, 60], [20, 100], [30, 120]], 50); // 220

Почему не жадность

Жадный выбор по value/weight оптимален только для дробного рюкзака. В примере выше он возьмёт предметы весом 10 и 20 (ценность 160), а оптимум — 20 и 30 (220).

Нюансы

• O(n·W) — псевдополиномиально: W экспоненциально в битах входа, задача NP-трудная.
• Чтобы восстановить набор, нужна двумерная таблица и обратный проход от dp[n][W].
• Если W огромный, а ценности маленькие, считают ДП по ценности: минимальный вес для каждой суммарной ценности.

Коротко для собеседования

Рюкзак 0/1 решается ДП по вместимости: для каждого предмета решаем, брать его или нет, и храним лучшую ценность для каждого веса. Главная ловушка — обходить вместимость по возрастанию, это уже неограниченный рюкзак; при n ≈ 40 и огромном W помогает meet-in-the-middle.