Задача о рюкзаке

Задача о рюкзаке (knapsack problem) — классическая задача оптимизации: выбрать предметы с весами и стоимостями, чтобы максимизировать суммарную стоимость при ограничении суммарного веса.

Зачем нужно

Задача о рюкзаке — архетип NP-трудных задач оптимизации и одна из самых популярных задач на собеседованиях. Она демонстрирует применение динамического программирования, разницу между вариантами (0/1 vs дробный), и понятие псевдополиномиального алгоритма. Её решение лежит в основе многих реальных задач ресурсного планирования.

Где используется

  • Ресурсное планирование: выбор проектов с бюджетом и ожидаемой прибылью
  • Криптография: задача о рюкзаке как основа криптосистем (Merkle-Hellman)
  • Финансовые задачи: оптимизация портфеля активов
  • Задачи разрезания материала (cutting stock problem)

Основной контент

Варианты задачи

Вариант Описание Метод
0/1 Knapsack Каждый предмет берётся 0 или 1 раз DP — O(n·W)
Unbounded Knapsack Предмет можно брать неограниченно DP — O(n·W)
Fractional Knapsack Можно брать часть предмета Жадный — O(n log n)

0/1 Knapsack — DP решение

/**
 * @param {number} weights - веса предметов
 * @param {number} values  - стоимости предметов
 * @param {number}   W       - вместимость рюкзака
 * @returns {number} максимальная стоимость
 */
function knapsack01(weights, values, W) {
  const n = weights.length;
  // dp[i][w] = макс. стоимость при i предметах и вместимости w
  const dp = Array.from({ length: n + 1 }, () => new Array(W + 1).fill(0));

  for (let i = 1; i <= n; i++) {
    for (let w = 0; w <= W; w++) {
      // не берём предмет i
      dp[i][w] = dp[i-1][w];
      // берём предмет i (если помещается)
      if (weights[i-1] <= w) {
        dp[i][w] = Math.max(dp[i][w],
                            dp[i-1][w - weights[i-1]] + values[i-1]);
      }
    }
  }
  return dp[n][W];
}

// Пример
const weights = [2, 3, 4, 5];
const values  = [3, 4, 5, 6];
const W = 8;
console.log(knapsack01(weights, values, W)); // 10 (предметы 0+3: вес 7, стоим. 9)
                                              // или 1+2: вес 7, стоим. 9

Оптимизация по памяти — O(W)

function knapsack01Optimized(weights, values, W) {
  const dp = new Array(W + 1).fill(0);
  // Важно: перебирать w справа налево!
  for (let i = 0; i < weights.length; i++) {
    for (let w = W; w >= weights[i]; w--) {
      dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
    }
  }
  return dp[W];
}

Fractional Knapsack — жадный O(n log n)

function fractionalKnapsack(weights, values, W) {
  const items = weights.map((w, i) => ({
    weight: w, value: values[i],
    ratio: values[i] / w  // ценность на единицу веса
  }));
  items.sort((a, b) => b.ratio - a.ratio); // сортируем по убыванию ratio

  let totalValue = 0, remaining = W;
  for (const item of items) {
    if (remaining <= 0) break;
    const take = Math.min(item.weight, remaining);
    totalValue += take * item.ratio;
    remaining -= take;
  }
  return totalValue;
}

Восстановление ответа (backtracking)

function getItems(weights, values, W, dp) {
  const n = weights.length;
  const chosen = ;
  let w = W;
  for (let i = n; i > 0; i--) {
    if (dp[i][w] !== dp[i-1][w]) { // предмет i был взят
      chosen.push(i - 1);
      w -= weights[i - 1];
    }
  }
  return chosen;
}

Частые ошибки

  • В оптимизированной версии перебирать w слева направо вместо справа налево — предмет будет учтён несколько раз (это уже unbounded knapsack).
  • Путать 0/1 и fractional: для дробного жадный оптимален, для 0/1 — нет.
  • Забывать, что алгоритм псевдополиномиальный: O(n·W), а не полиномиальный — при больших W неприменим.
  • Не восстанавливать сам набор предметов — часто задача требует именно список, а не только максимальную стоимость.

Связанные темы

Ресурсы