Подготовка к алгоритмическим задачам

Задача о рюкзаке: подробный разбор решения

12 мин чтения

алгоритмы

динамическое программирование

оптимизация

рекурсия

жадные алгоритмы

Почему эта задача важна?

Задача о рюкзаке — это фундаментальная проблема оптимизации, которая позволяет оценить:

🧠 Понимание принципов динамического программирования
⚡ Навыки решения задач оптимизации с ограничениями
🎯 Способность выбирать между различными алгоритмическими подходами
🔍 Умение применять рекурсию и мемоизацию
💼 Практические навыки решения реальных бизнес-задач

Постановка задачи

Классическая формулировка (0/1 задача о рюкзаке):

Дан набор предметов, каждый с определенным весом и ценностью. Требуется определить, какие предметы взять с собой в рюкзак, чтобы их суммарная ценность была максимальной, а суммарный вес не превышал заданную грузоподъемность рюкзака.

При этом каждый предмет можно взять только один раз (0/1) или не брать вовсе.

Математическая формулировка:

Максимизировать: $\sum_{i=1}^{n} v_i \cdot x_i$

При условии: $\sum_{i=1}^{n} w_i \cdot x_i \leq W$

Где:

$n$ — количество предметов
$v_i$ — ценность i-го предмета
$w_i$ — вес i-го предмета
$W$ — грузоподъемность рюкзака
$x_i$ — бинарная переменная (0 или 1), показывающая, берем ли мы i-й предмет

Примеры:

// Первый пример ✅
Input: 
weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
capacity = 8

Output: 9
Объяснение: Максимальная ценность достигается при выборе предметов с весами [3, 5] и ценностями [4, 6]

// Второй пример ✅
Input:
weights = [1, 2, 3, 5]
values = [1, 5, 4, 7]
capacity = 7

Output: 13
Объяснение: Максимальная ценность достигается при выборе предметов с весами [2, 5] и ценностями [5, 7] или [2, 3, 1] с ценностями [5, 4, 1]

Пройди собеседование в топ-компанию

Платформа для подготовки

Решай алгоритмические задачи как профи

✓ Популярные алгоритмы✓ Разбор решений✓ AI помощь

Начать сейчас→

Подходы к решению

Решение 1: Полный перебор (рекурсивный подход) 🔍

function knapsackBruteForce(weights, values, capacity, n) {
  // Базовый случай: нет предметов или нет места
  if (n === 0 || capacity === 0) {
    return 0;
  }
  
  // Если вес n-го предмета больше вместимости рюкзака,
  // не включаем его в решение
  if (weights[n - 1] > capacity) {
    return knapsackBruteForce(weights, values, capacity, n - 1);
  }
  
  // Возвращаем максимум из двух случаев:
  // 1. n-й предмет включен
  // 2. n-й предмет не включен
  else {
    const includeItem = values[n - 1] + knapsackBruteForce(
      weights, values, capacity - weights[n - 1], n - 1
    );
    const excludeItem = knapsackBruteForce(
      weights, values, capacity, n - 1
    );
    
    return Math.max(includeItem, excludeItem);
  }
}

// Вызов функции
function solveKnapsack(weights, values, capacity) {
  return knapsackBruteForce(weights, values, capacity, weights.length);
}

Анализ решения:

✅ Простая и понятная рекурсивная логика

✅ Корректно находит оптимальное решение

❌ Экспоненциальная временная сложность O(2^n)

❌ Многократный пересчет одних и тех же подзадач

Решение 2: Рекурсия с мемоизацией (нисходящее ДП) 🚀

function knapsackMemoization(weights, values, capacity, n, memo = {}) {
  // Ключ для хранения результата в кеше
  const key = `${n}:${capacity}`;
  
  // Проверяем, есть ли уже результат в кеше
  if (key in memo) {
    return memo[key];
  }
  
  // Базовый случай: нет предметов или нет места
  if (n === 0 || capacity === 0) {
    return 0;
  }
  
  // Если вес n-го предмета больше вместимости рюкзака
  if (weights[n - 1] > capacity) {
    memo[key] = knapsackMemoization(weights, values, capacity, n - 1, memo);
    return memo[key];
  }
  
  // Возвращаем максимум из двух случаев с мемоизацией
  else {
    const includeItem = values[n - 1] + knapsackMemoization(
      weights, values, capacity - weights[n - 1], n - 1, memo
    );
    const excludeItem = knapsackMemoization(
      weights, values, capacity, n - 1, memo
    );
    
    memo[key] = Math.max(includeItem, excludeItem);
    return memo[key];
  }
}

// Вызов функции
function solveKnapsack(weights, values, capacity) {
  return knapsackMemoization(weights, values, capacity, weights.length);
}

Характеристики:

✅ Значительное улучшение производительности по сравнению с полным перебором

✅ Временная сложность O(n × capacity)

✅ Избегает повторных вычислений с помощью мемоизации

❌ Глубина рекурсии может быть проблемой для больших входных данных

Решение 3: Динамическое программирование (восходящий подход) 📈

function knapsackDP(weights, values, capacity) {
  const n = weights.length;
  
  // Создаем таблицу DP размера (n+1) × (capacity+1)
  const dp = Array(n + 1)
    .fill()
    .map(() => Array(capacity + 1).fill(0));
  
  // Заполняем таблицу DP
  for (let i = 1; i <= n; i++) {
    for (let w = 0; w <= capacity; w++) {
      // Если текущий предмет не помещается в рюкзак
      if (weights[i - 1] > w) {
        dp[i][w] = dp[i - 1][w];
      } 
      // Иначе выбираем максимум из двух случаев
      else {
        dp[i][w] = Math.max(
          dp[i - 1][w],
          values[i - 1] + dp[i - 1][w - weights[i - 1]]
        );
      }
    }
  }
  
  // Восстанавливаем выбранные предметы
  const selectedItems = [];
  let i = n;
  let w = capacity;
  
  while (i > 0 && w > 0) {
    // Если значение изменилось, значит предмет был выбран
    if (dp[i][w] !== dp[i - 1][w]) {
      selectedItems.push(i - 1);  // Индекс предмета
      w -= weights[i - 1];
    }
    i--;
  }
  
  return {
    maxValue: dp[n][capacity],
    selectedItems: selectedItems.reverse()
  };
}

Преимущества и недостатки:

✅ Итеративный подход без использования рекурсии

✅ Оптимальная временная сложность O(n × capacity)

✅ Позволяет восстановить выбранные предметы

✅ Подходит для больших входных данных

❌ Требует дополнительной памяти O(n × capacity)

Решение 4: Оптимизированное ДП по памяти 🔧

function knapsackDPOptimized(weights, values, capacity) {
  const n = weights.length;
  
  // Используем только два массива вместо матрицы
  let prev = Array(capacity + 1).fill(0);
  let curr = Array(capacity + 1).fill(0);
  
  // Заполняем массивы
  for (let i = 1; i <= n; i++) {
    for (let w = 0; w <= capacity; w++) {
      if (weights[i - 1] > w) {
        curr[w] = prev[w];
      } else {
        curr[w] = Math.max(
          prev[w],
          values[i - 1] + prev[w - weights[i - 1]]
        );
      }
    }
    // Обновляем prev для следующей итерации
    [prev, curr] = [curr, prev];
  }
  
  // Результат находится в prev из-за последнего обмена
  return prev[capacity];
}

Особенности:

✅ Сокращает пространственную сложность до O(capacity)

✅ Сохраняет временную сложность O(n × capacity)

❌ Затрудняет восстановление выбранных предметов

❌ Немного сложнее для понимания из-за обмена массивов

Дробная задача о рюкзаке

В дробной задаче о рюкзаке (Fractional Knapsack) можно брать предметы по частям. Для этой версии задачи оптимальным является жадный алгоритм.

function fractionalKnapsack(weights, values, capacity) {
  const n = weights.length;
  
  // Вычисляем удельную ценность каждого предмета
  const valuePerWeight = weights.map((weight, index) => ({
    index,
    ratio: values[index] / weight
  }));
  
  // Сортируем по убыванию удельной ценности
  valuePerWeight.sort((a, b) => b.ratio - a.ratio);
  
  let totalValue = 0;
  let remainingCapacity = capacity;
  const selectedItems = [];
  
  // Жадно выбираем предметы с наибольшей удельной ценностью
  for (const item of valuePerWeight) {
    const index = item.index;
    const weight = weights[index];
    
    // Если предмет помещается целиком
    if (weight <= remainingCapacity) {
      totalValue += values[index];
      remainingCapacity -= weight;
      selectedItems.push({
        index: index,
        fraction: 1
      });
    }
    // Иначе берем часть предмета
    else {
      const fraction = remainingCapacity / weight;
      totalValue += values[index] * fraction;
      selectedItems.push({
        index: index,
        fraction: fraction
      });
      break; // Рюкзак заполнен
    }
  }
  
  return {
    maxValue: totalValue,
    selectedItems: selectedItems
  };
}

Анализ жадного алгоритма:

✅ Оптимален для дробной задачи о рюкзаке

✅ Временная сложность O(n log n) из-за сортировки

✅ Пространственная сложность O(n)

❌ Не подходит для классической 0/1 задачи о рюкзаке

Интуиция за динамическим программированием

Ключевая идея ДП для задачи о рюкзаке основана на разбиении проблемы на подзадачи:

Пусть dp[i][w] — максимальная ценность, которую можно получить, используя первые i предметов с вместимостью рюкзака w.

Тогда для каждого предмета у нас есть два варианта:

Не брать i-й предмет: dp[i][w] = dp[i-1][w]
Взять i-й предмет (если он помещается): dp[i][w] = values[i-1] + dp[i-1][w-weights[i-1]]

Мы выбираем максимум из этих двух вариантов, и это становится нашим рекуррентным соотношением для ДП.

Распространённые ошибки

🤦‍♂️ Забывание проверить, помещается ли предмет в рюкзак
😅 Неправильная инициализация таблицы ДП
🐛 Путаница с индексацией при восстановлении выбранных предметов
😕 Применение жадного алгоритма к 0/1 задаче о рюкзаке

Визуализация алгоритма ДП

Рассмотрим пример с:

Весами: [2, 3, 4, 5]
Ценностями: [3, 4, 5, 6]
Вместимостью рюкзака: 8

Таблица DP будет выглядеть так:

   w→| 0  1  2  3  4  5  6  7  8
i↓   |------------------------
0    | 0  0  0  0  0  0  0  0  0
1(2,3)| 0  0  3  3  3  3  3  3  3
2(3,4)| 0  0  3  4  4  7  7  7  7
3(4,5)| 0  0  3  4  5  7  8  9  9
4(5,6)| 0  0  3  4  5  7  8  9  9

Процесс восстановления выбранных предметов:

Начинаем с dp[4][8] = 9
Сравниваем с dp[3][8] = 9, значения одинаковы, значит, предмет 4 не выбран
Сравниваем dp[3][8] = 9 с dp[2][8] = 7, значения различны, значит, предмет 3 выбран
Переходим к dp[2][8-4] = dp[2][4] = 4
Сравниваем dp[2][4] = 4 с dp[1][4] = 3, значения различны, значит, предмет 2 выбран
Переходим к dp[1][4-3] = dp[1][1] = 0
Сравниваем dp[1][1] = 0 с dp[0][1] = 0, значения одинаковы, значит, предмет 1 не выбран

Итоговый выбор: предметы с индексами 2 и 3 (веса 3 и 4, ценности 4 и 5) Максимальная ценность: 9

Оптимизации

Ранняя остановка при малой вместимости

function knapsackEarlyStop(weights, values, capacity) {
  // Если вместимость рюкзака меньше минимального веса предмета
  const minWeight = Math.min(...weights);
  if (capacity < minWeight) {
    return 0;
  }
  
  // Основной алгоритм
  // ...
}

Сортировка предметов для эвристического ускорения

function knapsackSortedHeuristic(weights, values, capacity) {
  // Создаем массив предметов
  const items = weights.map((weight, index) => ({
    weight,
    value: values[index],
    ratio: values[index] / weight
  }));
  
  // Сортируем по убыванию отношения ценность/вес
  items.sort((a, b) => b.ratio - a.ratio);
  
  // Извлекаем отсортированные веса и ценности
  const sortedWeights = items.map(item => item.weight);
  const sortedValues = items.map(item => item.value);
  
  // Используем стандартный алгоритм ДП
  // с отсортированными предметами
  // ...
}

Использование битовых операций для экономии памяти

function knapsackBitOptimized(weights, values, capacity) {
  // Для небольших значений capacity можно использовать битовые операции
  // для отслеживания достижимых весов
  
  let reachable = 1; // Бит 0 установлен, так как вес 0 всегда достижим
  
  for (let i = 0; i < weights.length; i++) {
    // (reachable << weights[i]) представляет веса, достижимые
    // при добавлении текущего предмета
    reachable |= (reachable << weights[i]);
  }
  
  // Проверяем, какие веса достижимы
  for (let w = capacity; w >= 0; w--) {
    if ((reachable & (1 << w)) !== 0) {
      // Нашли максимальный достижимый вес
      // Теперь нужно вычислить максимальную ценность для этого веса
      // ...
      break;
    }
  }
}

Варианты задачи о рюкзаке

Многомерная задача о рюкзаке

Когда есть несколько ограничений (например, вес и объем):

function multiDimensionalKnapsack(weights, volumes, values, maxWeight, maxVolume) {
  const n = weights.length;
  
  // Создаем трехмерную таблицу DP
  const dp = Array(n + 1).fill().map(() => 
    Array(maxWeight + 1).fill().map(() => 
      Array(maxVolume + 1).fill(0)
    )
  );
  
  for (let i = 1; i <= n; i++) {
    for (let w = 0; w <= maxWeight; w++) {
      for (let v = 0; v <= maxVolume; v++) {
        // Если предмет не помещается
        if (weights[i - 1] > w || volumes[i - 1] > v) {
          dp[i][w][v] = dp[i - 1][w][v];
        } else {
          dp[i][w][v] = Math.max(
            dp[i - 1][w][v],
            values[i - 1] + dp[i - 1][w - weights[i - 1]][v - volumes[i - 1]]
          );
        }
      }
    }
  }
  
  return dp[n][maxWeight][maxVolume];
}

Задача о неограниченном рюкзаке

Когда каждый предмет можно брать неограниченное количество раз:

function unboundedKnapsack(weights, values, capacity) {
  const n = weights.length;
  const dp = Array(capacity + 1).fill(0);
  
  for (let w = 0; w <= capacity; w++) {
    for (let i = 0; i < n; i++) {
      if (weights[i] <= w) {
        dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
      }
    }
  }
  
  return dp[capacity];
}

Заключение

При решении задачи о рюкзаке важно помнить:

🤹‍♂️ Динамическое программирование — основной метод для 0/1 задачи о рюкзаке
📊 Жадный алгоритм оптимален только для дробной версии задачи
🧠 Правильное формулирование рекуррентного соотношения — ключ к решению с ДП
🔄 Оптимизации по памяти особенно важны при больших значениях вместимости

Эта задача служит фундаментальным примером применения динамического программирования и демонстрирует, как разбиение сложной проблемы на подзадачи может привести к эффективному алгоритму. Она имеет множество практических применений: от логистики и планирования ресурсов до финансовых инвестиций и оптимизации портфеля. 🌟

Попробуй решить популярные задачи

Массивы и Хеширование