# Как решить задачу о рюкзаке 0/1 на C#: подробный гайд с динамическим программированием

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

---

В современной разработке программного обеспечения умение решать задачи оптимизации является критически важным навыком, часто проверяемым на технических собеседованиях. Гэвин Лонг, эксперт и контрибьютор freeCodeCamp.org, представляет подробный разбор классической задачи о рюкзаке (0/1 Knapsack Problem), демонстрируя переход от неэффективного экспоненциального решения к оптимизированному алгоритму на языке C# с использованием динамического программирования.

## 🎒 Суть задачи о рюкзаке
[[JUMP:01:10]]

Задача формулируется через бытовую аналогию: человеку (в данном случае Гэвину, которого выселяет арендодатель) необходимо максимально быстро собрать вещи в рюкзак (knapsack) ограниченной емкости [01:22]. 

Ключевые условия задачи:

*   **Ограниченная вместимость**: контейнер (рюкзак) может выдержать строго определенный максимальный вес (в примере — 10 кг) [03:22].
*   **Дискретность (0/1)**: каждый предмет можно либо взять целиком (1), либо оставить (0). Его нельзя разделить на части [03:50].
*   **Цель**: максимизировать суммарную ценность выбранных предметов, не превысив лимит по весу [02:03].

В рассматриваемом примере фигурируют четыре предмета:

1.  Микроволновка (Microwave): 8 кг / $50.
2.  Дрон (Drone): 2 кг / $150.
3.  Монитор (Monitor): 6 кг / $210.
4.  Чайник (Kettle): 1 кг / $33.

## 📉 Сложность алгоритмов: от экспоненты к динамике
[[JUMP:04:03]]

Примитивный подход к решению заключается в переборе всех возможных комбинаций предметов. По словам Гэвина Лонга, если рассматривать каждый предмет как выбор «взять или нет», количество комбинаций составляет $2^n$, где $n$ — число предметов. Для четырех предметов это 16 вариантов, но для сотен предметов расчет станет невозможным для человека и слишком медленным для компьютера [04:18].

*   **Наивный подход**: временная сложность составляет $O(2^n)$ [04:30].
*   **Динамическое программирование**: использование метода «снизу вверх» (bottom-up approach) и мемоизации позволяет сократить сложность до $O(n \cdot W)$, где $W$ — максимальная вместимость рюкзака [04:44].

Мемоизация в данном контексте — это сохранение результатов решения подзадач в двумерном массиве (таблице), чтобы избежать повторных вычислений [07:08].

## 🏗️ Построение таблицы мемоизации
[[JUMP:07:20]]

Алгоритм заполняет таблицу, где строки представляют рассматриваемые предметы, а столбцы — инкрементальное увеличение вместимости рюкзака (от 0 до 10 кг) [07:47]. Каждая ячейка таблицы хранит максимально возможную ценность для данного набора предметов и данной вместимости.

Процесс заполнения ячейки `[i, j]` (где `i` — индекс предмета, `j` — текущая вместимость) подчиняется следующей логике:

1.  **Если предмет не влезает**: если вес текущего предмета больше текущей вместимости `j`, мы берем значение из ячейки ровно над текущей (результат для того же веса, но без этого предмета) [16:01].
2.  **Если предмет влезает**: мы выбираем максимум из двух вариантов с помощью функции `Math.Max`:
    *   Оставить всё как было (значение ячейки над текущей).
    *   Взять текущий предмет: его ценность + ценность, которую мы могли получить с оставшимся свободным весом (значение в предыдущей строке со смещением влево на вес текущего предмета) [15:24].

Результат всей задачи всегда находится в самой нижней правой ячейке таблицы (в нашем случае — позиция `[4, 10]`) [16:41].

## 💻 Реализация на C#
[[JUMP:10:02]]

Для решения задачи в Visual Studio создается консольное приложение на .NET Core [09:25]. Основные этапы кодирования:

1.  **Подготовка данных**: создаются массивы целых чисел для весов и ценностей предметов:
    *   `int[] weights = { 8, 2, 6, 1 };`
    *   `int[] values = { 50, 150, 210, 30 };` [10:16]
2.  **Инициализация таблицы**: создание двумерного массива `int[,] data = new int[n + 1, capacity + 1]` [10:41].
3.  **Вложенные циклы**: внешний цикл проходит по предметам, внутренний — по весам от 0 до MaxCapacity [11:06].
4.  **Условие 0-й строки/столбца**: ячейки, где индекс предмета или вес равны 0, заполняются нулями для корректной работы последующих вычислений [13:46].

При запуске этого алгоритма для текущего набора данных итоговая ценность составила $390 [17:27]. В рюкзак попали Дрон, Монитор и Чайник.

## 🔍 Обратный поиск выбранных предметов
[[JUMP:38:30]]

Мало знать максимальную ценность, нужно понимать, какие именно предметы её обеспечили. Для этого Гэвин предлагает алгоритм обратного хода (backtracking) [41:21]:

*   Начинаем с итоговой ячейки `[4, 10]`.
*   Сравниваем значение текущей ячейки со значением в ячейке над ней.
*   **Если значения равны**: значит, текущий предмет не добавил ценности и не был включен. Переходим в ячейку выше [42:43].
*   **Если значения различаются**: значит, текущий предмет включен в рюкзак. Мы отмечаем его, вычитаем его вес из текущей вместимости `j` и переходим в ячейку выше в новый столбец [43:47].

Для визуализации Лонг реализует вспомогательный метод `WriteTextToScreen`, который окрашивает названия взятых предметов в зеленый цвет (success), а оставленных — в красный (danger) [44:53]. Такой подход наглядно демонстрирует работу алгоритма оптимизации в реальном времени.