Где применяется
1. Задача
Ты ведёшь рекламную кампанию с фиксированным бюджетом, скажем 5000. Перед тобой список размещений. У каждого есть цена и ожидаемая польза, ценность. Каждое размещение покупают целиком или не покупают, половину слота взять нельзя.
Какой набор размещений даст больше всего ценности и не выйдет за бюджет? Первое, что приходит в голову: перебрать все возможные наборы. С 10 размещениями их 1024, это нормально. С 40 их больше триллиона, и перебор растянется на часы.
Это задача о рюкзаке 0/1 (0/1 knapsack), одна из самых частых форм DP в реальной работе. «0/1» значит, что каждый предмет либо берут целиком (1), либо не берут (0).
Этот шаг из платной части
Бесплатные шаги в начале курса (их 33) открыты всем: урок, задача и тесты. Этот шаг открывается с полным доступом. Начни с бесплатного аккаунта и бесплатных шагов.
Завести бесплатный аккаунтПосмотреть, что входитКак узнать
Эти слова в условии значат этот паттерн
- лучшее/максимум/минимум, заканчивающееся в позиции i
- число способов дойти, подняться или замостить
- нельзя брать два соседних элемента
- минимальная стоимость пути по сетке
- повторяющиеся подзадачи, одно и то же состояние считается заново
Похоже, но не то
- Рекурсия с мемоизацией (Recursion with memoization)
Мемоизация заполняет ту же таблицу сверху и по требованию. Здесь она заполняется снизу в заданном порядке.
- Жадный алгоритм (обменный аргумент) (Greedy (exchange argument))
Жадность выбирает один вариант на шаг. Динамика держит все варианты до конца.
- Рекурсия (Recursion)
Рекурсия показывает, каким будет переход. Скорость даёт именно таблица.
- DP над подпоследовательностями (LIS / LCS / расстояние редактирования) (DP on subsequences (LIS / LCS / edit distance))
Там состояние это пара позиций в двух последовательностях. Здесь хватает одного индекса.
n состояний по O(1) работы дают O(n). Память падает до O(1), когда важны только последние состояния.
На LeetCode
Задачи, где каждый предмет либо берут один раз, либо оставляют, при ограничении, например разбить массив на две равные суммы или получить цель, расставив плюсы и минусы. Таблица строится по предмету и оставшейся вместимости.
Вместимость это половина общей суммы, и вопрос в том, заполняет ли её какое-то подмножество ровно.
Числа со знаком плюс должны дать (сумма + цель) / 2, так что посчитай подмножества, которые дают ровно эту вместимость.
Раздели камни на две группы, как можно ближе по весу. Рюкзак вместимостью в половину суммы находит самую тяжёлую группу, которая помещается.
Каждая строка стоит сколько-то нулей и сколько-то единиц, поэтому вместимость состоит из двух чисел и у таблицы появляется второе измерение вместимости.