Алгоритмы
Knapsack: Задача о рюкзаке
Цели урока
- Понимать формулировку 0/1 Knapsack
- Реализовать рекурсивное и DP решение
- Оптимизировать память до O(W)
- Понимать разницу 0/1 vs Unbounded
- Решать вариации: Subset Sum, Coin Change
Предварительные знания
- Динамическое программирование
Задача о рюкзаке - одна из самых важных в комбинаторной оптимизации. Её изучают криптографы (основа некоторых шифров), экономисты (оптимизация портфеля), логисты (загрузка контейнеров). На собеседованиях - must know.
- Загрузка грузовиков и контейнеров
- Инвестиционные портфели
- Распределение ресурсов
- Криптография (Merkle-Hellman)
История задачи о рюкзаке
Задача формализована в 1897 году Джорджем Данцигом. Доказано NP-полной в 1972 (Karp). Несмотря на это, DP решение O(nW) работает быстро для практических случаев - это псевдополиномиальный алгоритм.
Формулировка задачи
**Задача о рюкзаке:** есть n предметов с весами и ценностями. Вместимость рюкзака W. Какие предметы взять, чтобы максимизировать суммарную ценность?
**Варианты задачи:**
- **0/1 Knapsack**: каждый предмет можно взять 0 или 1 раз
- **Unbounded Knapsack**: предметы можно брать неограниченно
- **Bounded Knapsack**: у каждого предмета своё ограничение
- **Fractional Knapsack**: можно брать части предметов (жадный!)
**0/1 Knapsack - NP-полная задача!** Но псевдополиномиальное DP решение работает быстро для разумных W.
Чем 0/1 Knapsack отличается от Fractional Knapsack?
Рекурсивное решение
**Для каждого предмета два выбора:** взять или не взять.
Почему рекурсивное решение O(2^n)?
DP решение: 2D таблица
**dp[i][w]** = максимальная ценность, используя первые i предметов при вместимости w.
**Восстановление выбранных предметов:**
weights=[2,3,4], values=[3,4,5], W=5. Максимальная ценность?
Оптимизация до O(W) памяти
**Ключевое наблюдение:** dp[i][w] зависит только от dp[i-1][...]. Нужна одна строка!
**Unbounded Knapsack - можно брать неограниченно:**
**0/1 → справа налево. Unbounded → слева направо.** Направление определяет, можно ли использовать предмет повторно.
Почему в 0/1 Knapsack итерируем по w справа налево?
Вариации и применения
**Subset Sum - частный случай Knapsack:**
**Coin Change - вариация Unbounded:**
**Паттерн:** многие задачи сводятся к Knapsack. Subset Sum, Partition, Coin Change, Target Sum - всё это вариации.
Задача 'можно ли разбить массив на две части с равной суммой' - это:
Knapsack
- 0/1: каждый предмет 0 или 1 раз
- DP: dp[i][w] = max(не брать, брать)
- Оптимизация: одна строка, итерация справа налево
- Unbounded: слева направо (повторения)
- Subset Sum, Coin Change, это вариации
Связанные темы
Knapsack - центральная задача оптимизации.
- DP основы — Базовая парадигма
- Жадные алгоритмы — Fractional Knapsack решается жадно
- NP-полнота — Knapsack - NP-полная задача
Связанные уроки
- alg-21-dp — Рюкзак - модельная задача 2D-оптимизации через DP
- alg-20-greedy — Жадность решает дробный рюкзак, но проваливает 0/1
- alg-34-approximation — Для рюкзака существует FPTAS-схема приближения
- crypto-24-rsa-math — Сложность рюкзака лежит в основе ранних криптосистем с открытым ключом
- ml-01-intro