Алгоритмы с нуля

Задача о рюкзаке 0/1 и сумма подмножества: максимизировать ценность при ограничении по весу

Суть Рюкзак 0/1: предметы с весом и ценностью, ёмкость W, максимизируй ценность, беря каждый предмет 0 или 1 раз. Состояние dp[i][w] = max(пропустить, взять если влезает). Сумма подмножества — булев частный случай. Одномерная форма идёт по ёмкости вниз. O(n*W), псевдополиномиально.

◷ 30 min

Ты вор с сумкой что вмещает максимум 5 килограммов. Перед тобой лежат предметы, каждый со своим весом и ценностью, и каждый можно схватить только раз — он попадает в сумку или остаётся. Какое множество предметов максимизирует ценность с которой ты уйдёшь? Нельзя просто жадно схватить самый ценный предмет; он может оказаться слишком тяжёлым и вытеснить два более дешёвых предмета что вместе дадут лучший результат. Это задача о рюкзаке 0/1, и это каноническая двухосевая динамическая программа: одна ось это “какие предметы я уже рассмотрел”, другая это “сколько ёмкости осталось”. Освой эту задачу, и вместе с ней решится целое семейство задач “выбери подмножество в рамках бюджета” — включая сумму подмножества, булевым упрощенным вариантом что просто спрашивает: может ли какое-то подмножество попасть точно в цель?

Цель

После этого урока ты можешь решить задачу о рюкзаке 0/1 с таблицей DP: состояние dp[i][w] это лучшая ценность используя первые i предметов в рамках ёмкости w, а рекуррента в каждой ячейке это максимум из пропустить предмет i (dp[i-1][w]) и взять предмет i (dp[i-1][w-wt[i]] + val[i], только если влезает). Ты можешь решить сумму подмножества как булеву специализацию — замени max на OR и ценность на “достижимо”. Ты можешь свернуть 2D таблицу в одномерный скользящий массив, и — это важный нюанс, который нельзя упустить — ты можешь объяснить почему внутренний цикл по ёмкости должен идти вниз для 0/1 (так каждый предмет используется максимум раз) и почему вверх вместо этого даёт безграничный рюкзак (предметы переиспользуемы). Ты можешь сформулировать сложность по времени O(n·W) и объяснить почему она только псевдо-полиномиальная: W это числовое значение, не количество входов, так что стоимость может взорваться даже для крошечного списка предметов. Следующий юнит переходит от этих одномерных DP по ёмкости к более сложным структурам.

Идея

Задача, сформулированная точно

У тебя n предметов. Предмет i имеет вес wt[i] и ценность val[i]. У тебя рюкзак с ёмкостью по весу W. Выбери подмножество предметов так чтобы общий вес был не больше W а общая ценность была как можно больше. “0/1” значит что каждый предмет либо целиком внутри (1) либо целиком снаружи (0) — никаких дробей, никаких дубликатов.

Почему жадность проваливается

Соблазнительная жадная идея — хватать наибольшую ценность, или лучшую ценность-на-вес, пока сумка не полна — не работает для 0/1. Один предмет высокой плотности может заблокировать лучшую комбинацию других. Пример: ёмкость 5, предметы (вес 2, ценность 3), (вес 3, ценность 4), (вес 4, ценность 5). Лучший предмет по ценности-на-вес это первый (1.5 на кг), но оптимальный ответ берёт предметы 1 и 2 на вес 5 и ценность 7 — побеждая любой одиночный захват. Тебе нужно рассмотреть комбинации, и это то что делает DP.

Состояние и рекуррента

Определи состояние как 2D таблицу:

dp[i][w] = the maximum value achievable using only the first i items,
           with total weight not exceeding w.

Для каждого предмета i (i-й предмет, индексация с 1) и каждой ёмкости w ты встречаешь ровно два выбора:

Пропустить предмет i. Тогда лучшее что ты можешь сделать это то чем dp[i-1][w] уже было — та же ёмкость, на один предмет меньше для рассмотрения.
Взять предмет i (легально только если влезает, wt[i] <= w). Ты тратишь wt[i] ёмкости и получаешь val[i], поверх лучшего что ты мог сделать с первыми i-1 предметами в оставшейся ёмкости: dp[i-1][w - wt[i]] + val[i].

Возьми лучшее из двух:

dp[i][w] = max( dp[i-1][w],                          // skip item i
                dp[i-1][w - wt[i]] + val[i] )         // take item i (if wt[i] <= w)

Ветка “взять” тянется в строку i-1, не в строку i. Это вся причина почему каждый предмет используется максимум раз: когда ты решаешь про предмет i, ты строишь на состоянии что ещё не видело предмет i.

Базовый случай: dp[0][w] = 0 для каждого w — с нулём предметов лучшая ценность это 0 независимо от ёмкости. Ответ на всю задачу это dp[n][W].

Заполнение таблицы (разобранный пример)

Предметы (вес 2, ценность 3), (вес 3, ценность 4), (вес 4, ценность 5), ёмкость W = 5. Строки это рассмотренные предметы (i = 0..3), столбцы это ёмкость (w = 0..5):

        w=0  w=1  w=2  w=3  w=4  w=5
i=0      0    0    0    0    0    0     no items: all zero
i=1      0    0    3    3    3    3     item (2,3): fits from w=2 on
i=2      0    0    3    4    4    7     item (3,4): w=5 -> take it + dp[1][2]=3 -> 7
i=3      0    0    3    4    5    7     item (4,5): w=5 keeps 7 (skip beats take=5)

Прочитай последнюю ячейку: dp[3][5] = 7. Проследи одну интересную ячейку — dp[2][5]: пропустить даёт dp[1][5] = 3; взять даёт dp[1][5-3] + 4 = dp[1][2] + 4 = 3 + 4 = 7. Максимум это 7. Таблица только что открыла “взять предметы 1 и 2”.

Сумма подмножества: булева специализация

Сумма подмножества задаёт вопрос да/нет: даны числа и цель T, складывается ли какое-то подмножество точно в T? Это задача о рюкзаке 0/1 где каждое число это предмет чей вес и ценность оба равны числу, и тебя волнует только достижима ли сумма. Так замени max на логическое OR а ценность на булево “достижимо”:

reach[i][t] = true if some subset of the first i numbers sums to exactly t.
reach[i][t] = reach[i-1][t]              (skip number i)
            OR reach[i-1][t - num[i]]    (take number i, if num[i] <= t)

Базовый случай reach[i][0] = true (пустое подмножество складывается в 0). Ответ это reach[n][T]. Тот же скелет пропустить-или-взять, просто булевы вместо текущего максимума.

Код

Рюкзак 0/1 с 2D таблицей

Это строит точную таблицу из разобранного примера выше. Заметь как каждое “взять” читает из предыдущей строки, dp[i-1].


      1
      function knapsack(weights, values, W) {
    

      2
      const n = weights.length;
    

      3
      // dp[i][w] = best value using first i items within capacity w
    

      4
      const dp = Array.from({ length: n + 1 }, () => new Array(W + 1).fill(0));
    

      5
       
    

      6
      for (let i = 1; i <= n; i++) {
    

      7
        const wt = weights[i - 1];
    

      8
        const val = values[i - 1];
    

      9
        for (let w = 0; w <= W; w++) {
    

      10
          dp[i][w] = dp[i - 1][w];                 // skip item i
    

      11
          if (wt <= w) {                           // does item i fit?
    

      12
            dp[i][w] = Math.max(
    

      13
              dp[i][w],
    

      14
              dp[i - 1][w - wt] + val              // take item i
    

      15
            );
    

      16
          }
    

      17
        }
    

      18
      }
    

      19
      return dp[n][W];                             // best value, all items, full capacity
    

      20
      }

L4 Строка 0 это все нули (нет предметов = нет ценности); Array.fill(0) задаёт каждую ячейку, так базовый случай бесплатен.
L6 Внешний цикл: вводи предмет i в рассмотрение, один предмет на строку.
L10 Ветка пропуска: лучшее без предмета i это ровно значение прошлой строки при той же ёмкости.
L11 Взять легально только когда предмет влезает в текущую ёмкость w.
L13 Ветка взять читает dp[i-1] (предыдущую строку), НЕ dp[i] — это то что держит каждый предмет использованным максимум раз.
L19 Ответ живёт в нижней-правой ячейке: все n предметов, полная ёмкость W.

Запуск (плюс одномерная скользящая форма и сумма подмножества)

2D версия, оптимизированная по памяти 1D скользящая версия и булева специализация суммы подмножества все возвращают тот же вид ответа из того же скелета.

// 0/1 knapsack: each item taken at most once, maximize value within capacity W
function knapsack(weights, values, W) {
const n = weights.length;
const dp = Array.from({ length: n + 1 }, () => new Array(W + 1).fill(0));
for (let i = 1; i <= n; i++) {
  const wt = weights[i - 1];
  const val = values[i - 1];
  for (let w = 0; w <= W; w++) {
    dp[i][w] = dp[i - 1][w];              // skip item i
    if (wt <= w) {                         // does item i fit?
      dp[i][w] = Math.max(dp[i][w], dp[i - 1][w - wt] + val); // take it
    }
  }
}
return dp[n][W];
}

const weights = [2, 3, 4];
const values  = [3, 4, 5];
const W = 5;
console.log("items (wt,val):", "(2,3) (3,4) (4,5)");
console.log("capacity W =", W);
console.log("0/1 knapsack best value =", knapsack(weights, values, W));

// 1D rolling: iterate capacity DOWNWARD so each item is used at most once
function knapsack1D(weights, values, W) {
const dp = new Array(W + 1).fill(0);
for (let i = 0; i < weights.length; i++) {
  const wt = weights[i], val = values[i];
  for (let w = W; w >= wt; w--) {          // downward = 0/1
    dp[w] = Math.max(dp[w], dp[w - wt] + val);
  }
}
return dp[W];
}
console.log("1D rolling best value  =", knapsack1D(weights, values, W));

// Subset sum: can a subset of nums add up exactly to target? boolean DP
function subsetSum(nums, target) {
const dp = new Array(target + 1).fill(false);
dp[0] = true;                              // empty subset hits 0
for (const num of nums) {
  for (let t = target; t >= num; t--) {    // downward, each number once
    if (dp[t - num]) dp[t] = true;
  }
}
return dp[target];
}
console.log("subset {3,34,4,12,5,2} -> 9? ", subsetSum([3, 34, 4, 12, 5, 2], 9));
console.log("subset {3,34,4,12,5,2} -> 30?", subsetSum([3, 34, 4, 12, 5, 2], 30));

Вывод

Одномерный скользящий массив и цикл вниз

2D таблица всегда читает только предыдущую строку, так тебе не нужно держать все строки — одного массива dp[w] достаточно если ты переиспользуешь его между предметами. Но есть подвох что решает корректность. После сведения к одному массиву, обновление предмета i это dp[w] = max(dp[w], dp[w - wt] + val). Ячейка dp[w - wt] должна всё ещё держать значение до того как предмет i был обработан (старую строку i-1). Если ты проходишь w вверх (от малого к большому), ты бы уже обновил dp[w - wt] предметом i до того как прочитал его — так ты мог бы добавить предмет i к состоянию что уже содержит предмет i, используя его дважды. Проход w вниз (от большого к малому) читает dp[w - wt] пока он всё ещё держит значение до-предмета-i, сохраняя правило “максимум раз”. Установи внутренний цикл как for (let w = W; w >= wt; w--) и 1D версия это ровно задача о рюкзаке 0/1.

Пошаговый разбор

Проследи одномерный скользящий массив на тех же предметах (вес 2, ценность 3), (вес 3, ценность 4), (вес 4, ценность 5) с W = 5. Массив начинается из всех нулей, индексы 0..5. Смотри как каждый предмет проходит ёмкость вниз так что ни одна ячейка которую он читает уже не поглотила текущий предмет.


      1
      dp = [0,0,0,0,0,0];                 // index 0..W
    

      2
      for each item (wt, val):
    

      3
        for (w = W; w >= wt; w--)         // DOWNWARD
    

      4
          dp[w] = max(dp[w], dp[w-wt] + val);
    

      5
      return dp[W];

Сложность

Время: O(n·W)

2D версия заполняет таблицу (n+1) x (W+1), и каждая ячейка делает O(1) работы (сравнение и максимум одно сложение). Итого: O(n·W). 1D скользящая версия делает то же число обновлений ячеек — n предметов умножить на до W ёмкостей — так она тоже O(n·W). Сумма подмножества идентична с целью T на месте W: O(n·T).

Память: O(W) со скользящим массивом

2D таблица стоит O(n·W) памяти. Но поскольку каждая строка читает только предыдущую строку, скользящий массив сворачивает это в единственный массив размера W+1: O(W) памяти (O(T) для суммы подмножества). Компромисс в том что ты теряешь полную таблицу, так что реконструкция того какие предметы были выбраны требует дополнительного учёта; если тебе нужна только лучшая ценность, скользящий массив строго лучше.

Почему O(n·W) только “псевдополиномиальная”

Это решающая тонкость. O(n·W) выглядит полиномиальной, но она не полиномиальна по размеру входа. Размер входа это число битов нужное чтобы его записать. Количество предметов n это настоящий счёт, но W это числовое значение, и значение W занимает лишь около log2(W) битов для кодирования. Так время работы n·W экспоненциально по числу битов W:

W = 1,000,000   ->  ~20 bits to write,  but the table has ~1,000,000 columns
double the bits of W (W = 2,000,000)  ->  the work doubles, not +constant

Алгоритм чья стоимость полиномиальна по числовому значению, но экспоненциальна по битовой длине этого значения, называется псевдополиномиальным. Для малого W (несколько тысяч) рюкзак быстрый и практичный. Для огромного W — скажем ёмкость в миллиардах с лишь горсткой предметов — таблица астрономически велика хотя вход помещается в одну строку. Это ровно почему задача о рюкзаке 0/1 NP-полна в общем случае: не известно алгоритма что полиномиален по размеру входа, только по значению W.

Безграничный рюкзак: та же стоимость, один цикл перевёрнут

Безграничный рюкзак (каждый предмет переиспользуем любое число раз) имеет то же время O(n·W) и память O(W). Единственная разница в коде это направление цикла по ёмкости — вверх вместо вниз — так что dp[w - wt] читается после того как он мог уже включить текущий предмет, позволяя взять его снова.

Практика 0 / 8

Что представляет состояние dp[i][w] в задаче о рюкзаке 0/1?

В рекурренте рюкзака 0/1, ветка 'взять предмет i' это dp[i-1][w - wt[i]] + val[i]. Почему она читает строку i-1 а не строку i?

В одномерной скользящей версии рюкзака 0/1, почему внутренний цикл по ёмкости должен идти ВНИЗ (от W вниз до wt)?

Какое одно изменение в 1D рюкзаке 0/1 превращает его в БЕЗГРАНИЧНЫЙ рюкзак (каждый предмет используем любое число раз)?

Как сумма подмножества (складывается ли какое-то подмножество точно в T?) это специализация задачи о рюкзаке 0/1?

Почему время O(n·W) задачи о рюкзаке 0/1 называется 'псевдополиномиальным' а не истинно полиномиальным?

Рюкзак 0/1 с ёмкостью W = 5 и предметами (вес 2, ценность 3), (вес 3, ценность 4), (вес 4, ценность 5). Какова максимальная общая ценность?

Количество предметов n = 50 и ёмкость W = 2000. Примерно сколько ячеек имеет таблица DP рюкзака 0/1, считая сетку (n+1) на (W+1) грубо как n·W? Дай n·W.

Почему это работает

Почему две оси вместо одной? Более ранние DP в этом юните (Фибоначчи, подъём по лестнице) имели одну переменную состояния n. Рюкзаку нужны две потому что подзадача не полностью описана “сколько предметов рассмотрено” одним — тебе также нужно “сколько ёмкости осталось”, поскольку то же множество предметов ведёт себя по-разному при ёмкости 3 против ёмкости 30. Всякий раз когда решение потребляет общий ресурс (ёмкость, бюджет, время), этот ресурс обычно становится второй осью DP. Распознать “это задача выбери-подмножество-в-рамках-бюджета” это сигнал потянуться за таблицей рюкзака.

Частая ошибка

Баг цикла-вверх (классическая ошибка рюкзака). В 1D версии, написание внутреннего цикла как for (let w = wt; w <= W; w++) выглядит безобидно — оно даже компилируется и запускается — но молча решает не ту задачу. Проход вверх значит dp[w - wt] может уже включать текущий предмет к моменту когда ты читаешь его, так предмет считается несколько раз: ты написал безграничный рюкзак, не 0/1. Конкретно, один предмет (вес 2, ценность 3) с ёмкостью 6 возвращает 3 с корректным циклом вниз (взять раз) но 9 с циклом вверх (взять три раза). Если твой ответ 0/1 выходит подозрительно большим, проверь направление цикла первым делом.

Граничные случаи

Ёмкость ровно ноль, и предметы что не влезают. Когда W = 0, ни один предмет с положительным весом не влезает, так ответ это 0 — базовая строка обрабатывает это бесплатно поскольку dp[*][0] остаётся 0. Предмет тяжелее всей ёмкости (wt[i] > W) никогда не может быть взят; охрана if (wt <= w) просто пропускает его ветку “взять” при каждом w, так он ничего не вносит без особой обработки. Для суммы подмножества, dp[0] = true существенно: оно кодирует “пустое подмножество достигает сумму 0”, что засевает каждую достижимую сумму. Забудь эту одну инициализацию и вся булева таблица остаётся false.

Ещё практика

Восстановление выбранных предметов. Скользящий массив даёт лучшую ценность но не какие предметы были выбраны. Чтобы реконструировать выбор, держи полную 2D таблицу и иди назад от dp[n][W]: в ячейке dp[i][w], если dp[i][w] == dp[i-1][w] то предмет i был пропущен (перейди к dp[i-1][w]); иначе предмет i был взят (запиши его, перейди к dp[i-1][w - wt[i]]). Остановись на строке 0. Этот обратный ход это O(n) и стандартный способ превратить DP только-ценность в реальное решение — полезно и для случая суммы подмножества, когда тебе нужно подмножество а не только “да”.

Проверь себя

Викторина

Объясни DP рюкзака 0/1: состояние, рекурренту пропустить-или-взять, как сумма подмножества специализирует его, почему одномерный скользящий цикл должен идти вниз, и почему сложность псевдополиномиальная.

Итог

Задача о рюкзаке 0/1 максимизирует общую ценность по подмножеству предметов чей общий вес влезает в ёмкость W, беря каждый предмет 0 или 1 раз.

Состояние: dp[i][w] = лучшая ценность используя первые i предметов в рамках ёмкости w. Ответ: dp[n][W].

Рекуррента (пропустить или взять):

dp[i][w] = max( dp[i-1][w],                    // skip item i
                dp[i-1][w - wt[i]] + val[i] )  // take it (if wt[i] <= w)

Обе ветки читают строку i-1, что обеспечивает “каждый предмет использован максимум раз”.

Сумма подмножества это булева специализация: каждое число это предмет с весом = ценностью = числом, а max становится логическим OR по “достижима ли эта сумма?” с базовым случаем reach[0] = true.

Одномерный скользящий массив: сверни таблицу в один массив размера W+1. Внутренний цикл по ёмкости должен идти вниз (w от W до wt) так чтобы dp[w - wt] всё ещё держал значение до-предмета — предотвращая переиспользование. Переверни его вверх и получишь безграничный рюкзак (предметы переиспользуемы).

Сложность: время O(n·W), память O(W) со скользящим массивом. Это псевдополиномиальное: W это числовое значение требующее лишь ~log2(W) битов, так стоимость экспоненциальна по битовой длине входа, не полиномиальна по размеру входа — что и есть почему задача о рюкзаке 0/1 NP-полна в общем случае.

Следующий юнит идёт за пределы DP с одной ёмкостью к более богатым структурам состояния.

Продолжить восхождение ↑Наибольшая возрастающая подпоследовательность: ДП за O(n^2) и приём с массивом хвостов за O(n log n)