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

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

🎒 Суть задачи о рюкзаке 1:10

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

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

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

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

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

📉 Сложность алгоритмов: от экспоненты к динамике 4:03

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

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

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

🏗️ Построение таблицы мемоизации 7:20

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

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

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

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

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

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

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

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

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

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

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

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