Як розв'язується класична задача "про рюкзак" у динамічному програмуванні?

АлгоритмиJunior~2 хв читання

Коротка відповідь

Класична задача 0/1 «рюкзак» розв'язується динамічним програмуванням. Визначаємо стан dp[i][w] - максимальна цінність при використанні перших i предметів і обмеженні за вагою w. Перехід: dp[i][w] = max(dp[i-1][w], dp[i-1][w-weight[i]] + value[i]) при w ≥ weight[i], інакше dp[i][w] = dp[i-1][w]. Базові випадки: dp[0][w] = 0 і dp[i][0] = 0. Складність: O(n·W) за часом і O(n·W) за пам'яттю, оптимізується до O(W) за пам'яттю за однопрохідного оновлення w від W до 0.

Детальний розбір

Постановка

Дано n предметів, i-й предмет має вагу weight[i] і цінність value[i]. Є рюкзак місткістю W. Потрібно максимізувати сумарну цінність, не перевищуючи W. Кожен предмет можна взяти не більше одного разу (0/1).

Ідея динамічного програмування

Стан: dp[i][w] - максимальна цінність з використанням перших i предметів при допустимій вазі w.
Перехід:
Не беремо предмет i: dp[i-1][w].
Беремо предмет i (якщо weight[i] ≤ w): dp[i-1][w - weight[i]] + value[i]. Разом: dp[i][w] = max(dp[i-1][w], dp[i-1][w - weight[i]] + value[i]) при weight[i] ≤ w; інакше dp[i][w] = dp[i-1][w].
База: dp[0][w] = 0 для всіх w і dp[i][0] = 0 для всіх i.
Порядок обчислення: i від 1 до n, w від 0 до W.
Складність: час O(n·W); пам'ять O(n·W), оптимізується до O(W) з одновимірним масивом і зворотним проходом по w.

Приклад

weights = [3, 2, 4, 5], values = [4, 3, 5, 6], W = 8. Оптимально взяти предмети з вагами 3 і 5 (цінності 4 і 6): сумарна цінність = 10, сумарна вага = 8.

Реалізація (двовимірний DP + відновлення відповіді)

javascript

function knapsack01(weights, values, W) {
  const n = weights.length;
  const dp = Array.from({ length: n + 1 }, () => Array(W + 1).fill(0));
  const take = Array.from({ length: n + 1 }, () => Array(W + 1).fill(false));

  for (let i = 1; i <= n; i++) {
    const wt = weights[i - 1];
    const val = values[i - 1];
    for (let w = 0; w <= W; w++) {
      // Не беремо i-й предмет
      dp[i][w] = dp[i - 1][w];

      // Пробуємо взяти i-й предмет, якщо він поміщається
      if (wt <= w) {
        const candidate = dp[i - 1][w - wt] + val;
        if (candidate > dp[i][w]) {
          dp[i][w] = candidate;
          take[i][w] = true;
        }
      }
    }
  }

  // Відновлення обраних індексів предметів
  const chosenIndices = [];
  let w = W;
  for (let i = n; i >= 1; i--) {
    if (take[i][w]) {
      chosenIndices.push(i - 1);
      w -= weights[i - 1];
    }
  }
  chosenIndices.reverse();

  return { maxValue: dp[n][W], chosenIndices, dp }; // dp повертаємо опційно
}

// Приклад
const weights = [3, 2, 4, 5];
const values = [4, 3, 5, 6];
const W = 8;
const result = knapsack01(weights, values, W);
console.log(result); // { maxValue: 10, chosenIndices: [0, 3] }

Оптимізація за пам'яттю до O(W)

Щоб не перезаписувати значення поточної ітерації предмета, йдемо по w у зворотному порядку (від W до wt). У такому вигляді отримати набір предметів складніше без додаткових структур, але максимальну цінність обчислює коректно.

javascript

function knapsack01Optimized(weights, values, W) {
  const n = weights.length;
  const dp = Array(W + 1).fill(0);

  for (let i = 0; i < n; i++) {
    const wt = weights[i];
    const val = values[i];
    for (let w = W; w >= wt; w--) {
      dp[w] = Math.max(dp[w], dp[w - wt] + val);
    }
  }
  return dp[W];
}

// Приклад
console.log(knapsack01Optimized([3, 2, 4, 5], [4, 3, 5, 6], 8)); // 10

Типові підводні камені

Для одновимірного DP обов'язково проходити w від W до 0, інакше вийде «необмежений» рюкзак (кожен предмет можна буде використовувати багаторазово).
Відрізняйте рюкзак 0/1 від варіанта з необмеженою кількістю предметів і від «дробового» рюкзака (який розв'язується жадібно).
Коректно ініціалізуйте базу: рядок і стовпець із нульовими індексами - нулі.
Відновлення відповіді зручно зберігати через матрицю take[i][w] або батька; з одновимірним DP це складніше без додаткових структур.

Що важливо проговорити на співбесіді

Визначення стану dp і чому воно коректно моделює підзадачі.
Перехід і обґрунтування вибору max із двох варіантів (взяти/не брати).
База, порядок обходу і оцінка складності.
Оптимізація за пам'яттю до O(W) і чому потрібен зворотний прохід по w.
Як відновлювати набір предметів (через take/parent або зберігання додаткових даних).

Коротка відповідь

Для співбесіди

Premium

Коротка відповідь допоможе вам впевнено відповідати на цю тему під час співбесіди.