Классическая задача о рюкзаке является фундаментальной темой в компьютерных науках, знание которой часто проверяется на технических собеседованиях. В детальном руководстве от freeCodeCamp разработчик Гэвин Лонг демонстрирует, как уйти от неэффективного полного перебора вариантов и построить оптимальное решение на языке C#. С помощью динамического программирования и восходящего проектирования (bottom-up) автору удаётся превратить сложную оптимизационную задачу в элегантный табличный алгоритм.
📦 Постановка задачи: от выселения из квартиры до теории оптимизации 0:00
Задача о рюкзаке (Knapsack Problem) заслуженно считается эталоном для демонстрации возможностей динамического программирования и жадных алгоритмов. Гэвин Лонг, член команды freeCodeCamp, начинает разбор с шуточной, но жизненной аналогии. По сюжету, арендодатель выселяет его из квартиры из-за жалоб соседей на шум, полиция уже в пути, и герою нужно срочно собрать самые ценные вещи в походный рюкзак ограниченной вместимости. Цель проста — максимизировать общую стоимость взятого имущества, чтобы выручить деньги на залог за новое жильё.
В техническом плане рюкзак обладает конечной грузоподъёмностью, что накладывает жёсткие ограничения на выбор. В учебном примере рассматриваются четыре конкретных предмета:
- Микроволновая печь весом 8 кг и стоимостью $50.
- Квадрокоптер (дрон) весом 2 кг и стоимостью $150.
- Монитор весом 6 кг и стоимостью $210.
- Электрический чайник весом 1 кг и стоимостью $30.
Контейнер или рюкзак способен выдержать строго фиксированный вес, который в данном сценарии составляет 10 килограммов. Разработчику необходимо написать алгоритм, способный определить, какая именно комбинация вещей даст максимальную финансовую выгоду, не разорвав при этом сумку.
⏱️ Экспоненциальный взрыв против динамического программирования 3:36
Суть модификации задачи под названием «0/1 Knapsack» заключается в том, что каждый объект можно либо полностью взять (единица), либо полностью оставить (ноль). Дробление предметов не допускается. Если решать эту задачу «в лоб», перебирая все возможные подмножества элементов, программа столкнётся с комбинаторным взрывом.
Для $n$ предметов общее число потенциальных решений составляет $2^n$. В текущем примере с 4 объектами это всего $2^4 = 16$ комбинаций, что человек может посчитать вручную. Однако при масштабировании задачи до уровня реальных транспортных контейнеров со сотнями наименований грузов, время вычислений по экспоненциальной шкале Big O составит $O(2^n)$, что делает алгоритм неприменимым на практике. Подобные задачи оптимизации ежедневно выполняются в логистических компаниях для расчёта грузоперевозок, поэтому эффективность имеет критическое значение.
Гэвин Лонг объясняет, что применение динамического программирования кардинально меняет ситуацию, снижая временную сложность до псевдополиномиальной — $O(n \times W)$. В этой формуле $n$ означает количество рассматриваемых вещей, а $W$ — максимальный вес, который вмещает контейнер. Если суммарный вес предложенного решения превышает 10 кг, система должна мгновенно отбраковывать такую комбинацию.
📊 Метод снизу вверх и магия мемоизации 6:43
В данном уроке используется восходящий подход (bottom-up approach) к динамическому программированию. Это альтернатива нисходящему методу (top-down), и её главное преимущество заключается в том, что разработчик может полностью избежать написания сложного рекурсивного кода. Стратегия опирается на концепцию мемоизации.
Мемоизация гарантирует, что вычислительная функция никогда не будет запускаться для одних и тех же входных параметров более одного раза. Программа просто ведёт постоянный учёт и сохраняет уже найденные результаты подзадач. Для визуализации и хранения этих данных строится двумерная матрица (таблица).
Структура таблицы выглядит следующим образом:
- Каждая строка представляет собой отдельно рассматриваемый предмет.
- Каждый столбец обозначает текущую промежуточную вместимость рюкзака, которая инкрементируется на 1 единицу веса — от 0 до предельного значения 10.
Алгоритм последовательно обходит каждую ячейку таблицы слева направо, строка за строкой. В каждой точке вычисляется и фиксируется максимальная ценность груза для текущего набора предметов и текущей грузоподъёмности. Финальный и самый важный ответ всей задачи будет записан в самой последней, нижней правой ячейке таблицы — в позиции [4, 10].
💻 Реализация алгоритма на C#: заполнение матрицы данных 8:54
Практическая реализация начинается в среде Visual Studio с создания консольного приложения на базе .NET Core. Информацию о весах и стоимости предметов автор предлагает хранить в двух базовых одномерных массивах под названиями weights и values. Двумерный массив для мемоизации получает имя data. Также объявляются целочисленная константа n (число вещей) и переменная предельного веса рюкзака.
Основу вычислений составляют два вложенных цикла for. Внешний цикл итерируется по предметам, а внутренний отвечает за пошаговое увеличение рассматриваемой грузоподъёмности от 0 до 10 кг. Например, на третьем шаге внутреннего цикла алгоритм проверяет, выгодно ли брать вещь, если бы рюкзак вмещал всего 3 кг. Внутри этого цикла прописывается следующая логика:
Условие базовых нулевых значений
Если индекс предмета (itemNum) равен 0 или текущая тестируемая вместимость рюкзака (capacity) равна 0, в ячейку двумерного массива записывается жёсткий ноль. Заполнение первой строки и первого столбца нулями может показаться избыточным, но это технический фундамент, необходимый для корректной работы математических формул на следующих этапах вычислений.
Основное уравнение оптимизации
Если условия равенства нулю не выполняются, программа проверяет: укладывается ли вес текущего предмета в рамки рассматриваемой сейчас вместимости (else if). Если вес предмета меньше или равен текущей доступной емкости, запускается ключевая формула выбора с использованием статического метода Math.Max из стандартной библиотеки C#.
Метод Math.Max принимает два аргумента и возвращает наибольший из них:
- Ценность текущего предмета плюс максимальная ценность, которую можно было получить при оставшемся доступном весе на предыдущем шаге:
values[itemNum - 1] + data[itemNum - 1, capacity - weights[itemNum - 1]]. - Значение из ячейки строго над текущей позицией, то есть лучшая ценность для этой же вместимости, но без учёта нового предмета:
data[itemNum - 1, capacity].
Случай превышения веса
В ситуации, когда оба предыдущих ветвления возвращают ложь (else), это означает, что текущая вещь физически слишком тяжела для рассматриваемой в данный момент емкости рюкзака. В таком случае код просто дублирует значение из ячейки, находящейся прямо над ней. Результат работы всей этой конструкции выводится на экран из финальной точки data[n, MaxCapacity].
🔍 Пошаговый разбор: как заполняется таблица memoization 17:14
Запуск скомпилированной программы выдаёт итоговый результат — максимальная стоимость награбленного добра составляет $390. В рюкзак отправляются квадрокоптер, монитор и чайник. Чтобы досконально понять физику процесса, Гэвин Лонг подробно симулирует ручной обход матрицы.
Первая строчка (индекс 0) целиком забивается нулями. Переходя к первой реальной вещи — микроволновке (вес 8 кг, цена $50) — на позициях вместимости от 1 до 7 кг алгоритм записывает нули, так как её вес превышает доступный лимит, и срабатывает логика блока else (копирование значений сверху). Лишь на отметке в 8 кг условие else if становится истинным. Формула Math.Max сравнивает потенциальные $50 (цена микроволновки + 0 из ячейки data[0,0]) и 0 (значение сверху). В массив записывается 50, и это число удерживается до конца строки, включая емкости 9 и 10 кг.
На третьей строке рассчитывается дрон (вес 2 кг, цена $150). При емкости рюкзака в 1 кг он не влезает, и пишется 0. Начиная с емкости 2 кг и вплоть до 7 кг, алгоритм стабильно заносит значение 150. Однако на шаге с емкостью 8 кг формула выбирает между $150 (цена дрона + свободное место на 6 кг из верхней строки, где стоит 0) и ценой микроволновки в $50 из верхней ячейки. Число 150 побеждает. Самое интересное происходит на емкости 10 кг: программа понимает, что может взять и дрон ($150), и использовать оставшиеся 8 кг под микроволновку из предыдущей строки ($50). Сумма достигает $200, что больше, чем просто $50 сверху.
Далее оценивается монитор (6 кг, $210). До емкости 5 кг включительно таблица копирует верхние значения (150 за счёт дрона). На отметке 6 кг монитор вытесняет дрон, так как его личная цена $210 превосходит $150. На емкости 8 кг совершается новый прорыв: алгоритм берёт монитор ($210) и на оставшиеся 2 кг добирает дрон из верхней строки ($150), получая в сумме $360. Это значение сохраняется для емкостей 9 и 10 кг.
Последний предмет — чайник (1 кг, $30). На емкости 1 кг он даёт $30. На емкости 3 кг он сочетается с дроном ($30 + $150 = $180). На отметке в 7 кг чайник дополняет монитор ($30 + $210 = $240). Наконец, на отметке 9 кг формула выдаёт исторический максимум: чайник ($30) объединяется с комбинацией монитора и дрона на 8 кг ($360), обеспечивая итоговые $390. Эта же сумма дублируется для максимальной емкости в 10 кг.
🔄 Обратный ход: как узнать, какие именно вещи попали в рюкзак 38:00
Знать максимальную стоимость недостаточно — необходимо выдать пользователю конкретный список вещей для эвакуации. Автор проводит рефакторинг, вынося расчетную матрицу в отдельную функцию, и создаёт процедуру обратного восстановления ответа.
Логика обратного хода (backtracking) работает в противоположном направлении. Программа не начинает с нуля, а стартует из финальной правой нижней точки таблицы [4, 10] и движется назад к началу координат. Инициализируются переменные индексов i = n и j = MaxCapacity, запускается цикл while, который крутится, пока оба индекса строго больше нуля.
Внутри цикла выполняется сравнение текущей ячейки со значением, расположенным строго над ней:
- Если
data[i, j] == data[i - 1, j], это явный признак того, что текущий предметiне выбирался для оптимального набора, ведь его появление никак не увеличило общую ценность. Программа красит название предмета в консоли в красный цвет и уменьшает индекс строкiна единицу. - Если же значения различаются (
else), значит, предметiбыл успешно включен в рюкзак. Программа выводит его название зелёным цветом, вычитает вес этого предмета из текущей координатной вместимости (j = j - weights[i - 1]) и переходит к вышестоящей строке (i--).
Для красивого и наглядного отображения результатов в терминале Гэвин создаёт вспомогательный метод WriteTextToScreen и перечисление enum со статусами Normal, Success (зелёный фон для взятых вещей) и Danger (красный фон для оставленных предметов). Финальный тест написанного кода подтверждает стопроцентную точность работы алгоритма.
