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

Задача о рюкзаке: подробный разбор решения
Почему эта задача важна?
Задача о рюкзаке — это фундаментальная проблема оптимизации, которая позволяет оценить:
- 🧠 Понимание принципов динамического программирования
- ⚡ Навыки решения задач оптимизации с ограничениями
- 🎯 Способность выбирать между различными алгоритмическими подходами
- 🔍 Умение применять рекурсию и мемоизацию
- 💼 Практические навыки решения реальных бизнес-задач
Постановка задачи
Классическая формулировка (0/1 задача о рюкзаке):
Дан набор предметов, каждый с определенным весом и ценностью. Требуется определить, какие предметы взять с собой в рюкзак, чтобы их суммарная ценность была максимальной, а суммарный вес не превышал заданную грузоподъемность рюкзака.
При этом каждый предмет можно взять только один раз (0/1) или не брать вовсе.
Математическая формулировка:
Максимизировать:
При условии:
Где:
- — количество предметов
- — ценность i-го предмета
- — вес 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]
Решай алгоритмические задачи как профи

Подходы к решению
Решение 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 задачи о рюкзаке
- 📊 Жадный алгоритм оптимален только для дробной версии задачи
- 🧠 Правильное формулирование рекуррентного соотношения — ключ к решению с ДП
- 🔄 Оптимизации по памяти особенно важны при больших значениях вместимости
Эта задача служит фундаментальным примером применения динамического программирования и демонстрирует, как разбиение сложной проблемы на подзадачи может привести к эффективному алгоритму. Она имеет множество практических применений: от логистики и планирования ресурсов до финансовых инвестиций и оптимизации портфеля. 🌟