SprintCode.pro

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

Super

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

12 мин чтения
алгоритмы
динамическое программирование
оптимизация
рекурсия
жадные алгоритмы

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

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

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

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

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

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

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

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

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

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

Где:

  • nn — количество предметов
  • viv_i — ценность i-го предмета
  • wiw_i — вес i-го предмета
  • WW — грузоподъемность рюкзака
  • xix_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.

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

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

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

Рекомендации по решению 💡

  1. Выбор метода решения:

    • 🚀 Для стандартной задачи о рюкзаке лучше использовать ДП
    • 📝 Для дробной версии оптимален жадный алгоритм
    • 🧮 Если ограничения по памяти критичны, используйте оптимизированное ДП
  2. Важные моменты:

    • 📝 Правильно определите базовые случаи в рекурсии
    • 🔄 Не забудьте о возможности не выбирать предмет
    • 📊 Для восстановления выбранных предметов используйте обратный проход по таблице ДП

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

  1. 🤦‍♂️ Забывание проверить, помещается ли предмет в рюкзак
  2. 😅 Неправильная инициализация таблицы ДП
  3. 🐛 Путаница с индексацией при восстановлении выбранных предметов
  4. 😕 Применение жадного алгоритма к 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

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

  1. Начинаем с dp[4][8] = 9
  2. Сравниваем с dp[3][8] = 9, значения одинаковы, значит, предмет 4 не выбран
  3. Сравниваем dp[3][8] = 9 с dp[2][8] = 7, значения различны, значит, предмет 3 выбран
  4. Переходим к dp[2][8-4] = dp[2][4] = 4
  5. Сравниваем dp[2][4] = 4 с dp[1][4] = 3, значения различны, значит, предмет 2 выбран
  6. Переходим к dp[1][4-3] = dp[1][1] = 0
  7. Сравниваем 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 задачи о рюкзаке
  • 📊 Жадный алгоритм оптимален только для дробной версии задачи
  • 🧠 Правильное формулирование рекуррентного соотношения — ключ к решению с ДП
  • 🔄 Оптимизации по памяти особенно важны при больших значениях вместимости

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