# Гэвин Лонг представил пошаговое руководство по 0/1 Knapsack Problem на C#

Источник: https://www.youtube.com/watch?v=hagBB17_hvg
Канал: freeCodeCamp.org
Опубликовано: 25.09.2023

---

Классическая задача о рюкзаке является фундаментальной темой в компьютерных науках, знание которой часто проверяется на технических собеседованиях. В детальном руководстве от freeCodeCamp разработчик Гэвин Лонг демонстрирует, как уйти от неэффективного полного перебора вариантов и построить оптимальное решение на языке C#. С помощью динамического программирования и восходящего проектирования (bottom-up) автору удаётся превратить сложную оптимизационную задачу в элегантный табличный алгоритм.

## 📦 Постановка задачи: от выселения из квартиры до теории оптимизации
[[JUMP:0:00]]

Задача о рюкзаке (Knapsack Problem) заслуженно считается эталоном для демонстрации возможностей динамического программирования и жадных алгоритмов. Гэвин Лонг, член команды freeCodeCamp, начинает разбор с шуточной, но жизненной аналогии. По сюжету, арендодатель выселяет его из квартиры из-за жалоб соседей на шум, полиция уже в пути, и герою нужно срочно собрать самые ценные вещи в походный рюкзак ограниченной вместимости. Цель проста — максимизировать общую стоимость взятого имущества, чтобы выручить деньги на залог за новое жильё.

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

* Микроволновая печь весом 8 кг и стоимостью $50.
* Квадрокоптер (дрон) весом 2 кг и стоимостью $150.
* Монитор весом 6 кг и стоимостью $210.
* Электрический чайник весом 1 кг и стоимостью $30.

Контейнер или рюкзак способен выдержать строго фиксированный вес, который в данном сценарии составляет 10 килограммов. Разработчику необходимо написать алгоритм, способный определить, какая именно комбинация вещей даст максимальную финансовую выгоду, не разорвав при этом сумку.

## ⏱️ Экспоненциальный взрыв против динамического программирования
[[JUMP:3:36]]

Суть модификации задачи под названием «0/1 Knapsack» заключается в том, что каждый объект можно либо полностью взять (единица), либо полностью оставить (ноль). Дробление предметов не допускается. Если решать эту задачу «в лоб», перебирая все возможные подмножества элементов, программа столкнётся с комбинаторным взрывом.

Для $n$ предметов общее число потенциальных решений составляет $2^n$. В текущем примере с 4 объектами это всего $2^4 = 16$ комбинаций, что человек может посчитать вручную. Однако при масштабировании задачи до уровня реальных транспортных контейнеров со сотнями наименований грузов, время вычислений по экспоненциальной шкале Big O составит $O(2^n)$, что делает алгоритм неприменимым на практике. Подобные задачи оптимизации ежедневно выполняются в логистических компаниях для расчёта грузоперевозок, поэтому эффективность имеет критическое значение.

Гэвин Лонг объясняет, что применение динамического программирования кардинально меняет ситуацию, снижая временную сложность до псевдополиномиальной — $O(n \times W)$. В этой формуле $n$ означает количество рассматриваемых вещей, а $W$ — максимальный вес, который вмещает контейнер. Если суммарный вес предложенного решения превышает 10 кг, система должна мгновенно отбраковывать такую комбинацию.

## 📊 Метод снизу вверх и магия мемоизации
[[JUMP:6:43]]

В данном уроке используется восходящий подход (bottom-up approach) к динамическому программированию. Это альтернатива нисходящему методу (top-down), и её главное преимущество заключается в том, что разработчик может полностью избежать написания сложного рекурсивного кода. Стратегия опирается на концепцию мемоизации.

Мемоизация гарантирует, что вычислительная функция никогда не будет запускаться для одних и тех же входных параметров более одного раза. Программа просто ведёт постоянный учёт и сохраняет уже найденные результаты подзадач. Для визуализации и хранения этих данных строится двумерная матрица (таблица).



Структура таблицы выглядит следующим образом:

* Каждая строка представляет собой отдельно рассматриваемый предмет.
* Каждый столбец обозначает текущую промежуточную вместимость рюкзака, которая инкрементируется на 1 единицу веса — от 0 до предельного значения 10.

Алгоритм последовательно обходит каждую ячейку таблицы слева направо, строка за строкой. В каждой точке вычисляется и фиксируется максимальная ценность груза для текущего набора предметов и текущей грузоподъёмности. Финальный и самый важный ответ всей задачи будет записан в самой последней, нижней правой ячейке таблицы — в позиции `[4, 10]`.

## 💻 Реализация алгоритма на C#: заполнение матрицы данных
[[JUMP: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` принимает два аргумента и возвращает наибольший из них:

1.  Ценность текущего предмета плюс максимальная ценность, которую можно было получить при оставшемся доступном весе на предыдущем шаге: `values[itemNum - 1] + data[itemNum - 1, capacity - weights[itemNum - 1]]`.
2.  Значение из ячейки строго над текущей позицией, то есть лучшая ценность для этой же вместимости, но без учёта нового предмета: `data[itemNum - 1, capacity]`.

### Случай превышения веса
В ситуации, когда оба предыдущих ветвления возвращают ложь (`else`), это означает, что текущая вещь физически слишком тяжела для рассматриваемой в данный момент емкости рюкзака. В таком случае код просто дублирует значение из ячейки, находящейся прямо над ней. Результат работы всей этой конструкции выводится на экран из финальной точки `data[n, MaxCapacity]`.

## 🔍 Пошаговый разбор: как заполняется таблица memoization
[[JUMP: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 кг.

## 🔄 Обратный ход: как узнать, какие именно вещи попали в рюкзак
[[JUMP: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` (красный фон для оставленных предметов). Финальный тест написанного кода подтверждает стопроцентную точность работы алгоритма.