Динамічне програмування – задача про рюкзак

Повне пояснення

Коротке пояснення

Задача про рюкзак шукає найцінніший набір предметів, що вміщуються у рюкзак заданої ваги. Алгоритм використовує динамічне програмування, щоб уникнути повторного обчислення тих самих підзадач.

Аналогія

Уявіть, що ви йдете в магазин і маєте обмежений кошик. Ви розглядаєте кожен товар: чи варто його взяти, щоб отримати максимальну користь, не перевищуючи обмеження кошика.

Коли застосовувати

• Задача з обмеженою вагою рюкзака (0/1).
• Вхід: масив предметів з вагою та цінністю.
• Очікуваний результат: максимальна сумарна цінність, що не перевищує вагу.
• Підходить для невеликих до середніх розмірів (до кількох тисяч предметів).
• Не підходить, коли ваги дуже великі (пам’ять стає проблемою).

Кроки алгоритму

1. Створити двовимірну таблицю dp, де dp[i][w] – максимальна цінність з перших i предметів при вазі w.
2. Ініціалізувати dp[0][*] = 0 (без предметів – нульова цінність).
3. Для кожного предмету i від 1 до n:
   • Для кожної ваги w від 0 до W:
     • Якщо вага предмету > w, копіювати dp[i-1][w].
     • Інакше обрати максимум між dp[i-1][w] і dp[i-1][w - weight_i] + value_i.
4. Повернути dp[n][W].

Візуальна інтуїція (текстова)

Вага W = 5
Предмети: [{w:2,v:3},{w:3,v:4}]

dp[0] = [0,0,0,0,0,0]
dp[1] = [0,0,3,3,3,3]
dp[2] = [0,0,3,4,7,7]

Результат: 7 (обидва предмети)

Складність

• Час: O(n·W), де n – кількість предметів, W – максимальна вага рюкзака.
• Пам’ять: O(n·W) для повної таблиці, або O(W) при оптимізації одновимірним масивом.
• Найгірший випадок: коли всі предмети мають вагу 1, що збільшує розмір таблиці.

Код (js)

// Функція, що обчислює максимальну цінність рюкзака
function knapsack(items, maxWeight) {
  // items – масив об’єктів {weight, value}
  const n = items.length;
  // Створюємо двовимірну таблицю dp (n+1) x (maxWeight+1)
  const dp = Array.from({ length: n + 1 }, () => Array(maxWeight + 1).fill(0));

  // Проходимо по кожному предмету
  for (let i = 1; i <= n; i++) {
    const { weight, value } = items[i - 1]; // поточний предмет
    for (let w = 0; w <= maxWeight; w++) {
      if (weight > w) {
        // Якщо предмет важчий за поточну вагу, не можемо взяти його
        dp[i][w] = dp[i - 1][w];
      } else {
        // Вибираємо максимум між не взятим і взяттям предмету
        const without = dp[i - 1][w];
        const withItem = dp[i - 1][w - weight] + value;
        dp[i][w] = Math.max(without, withItem);
      }
    }
  }

  // Повертаємо максимальну цінність для повної ваги
  return dp[n][maxWeight];
}

// Тестовий приклад
const items = [
  { weight: 2, value: 3 },
  { weight: 3, value: 4 },
  { weight: 4, value: 8 }
];
console.log(knapsack(items, 5)); // очікуваний результат: 7

Типові помилки і поради

1. Використання неправильного індексу – пам’ятайте, що масив items починається з 0, а таблиця dp – з 1.
2. Неправильне порівняння ваги – перевірка weight > w повинна бути перед обчисленням максимуму.
3. Забудьте про 0‑ваговий рядок – без предметів цінність нульова, тому ініціалізація dp[0][*] = 0 критична.
4. Пам’ять – для великих W використовуйте одновимірний масив, оновлюючи з кінця до початку.
5. Оптимізація – можна обчислювати dp лише для ваг, що досяжні (наприклад, сумарна вага всіх предметів), щоб зменшити розмір таблиці.

Перевір себе

1. Яка складність часу для n предметів і максимальної ваги W?
2. Що робить рядок dp[i][w] = Math.max(without, withItem);?