Неограниченный рюкзак и размен монет II

В задаче о неограниченном рюкзаке каждый элемент можно брать любое количество раз (в отличие от рюкзака 0/1, где каждый элемент используется не более одного раза). Определение состояния остаётся тем же: dp[c] = максимальная ценность, достижимая при вместимости c, — но направление перебора меняется. Поскольку элементы можно использовать повторно, при обновлении dp[c] нужно разрешить повторное использование текущего элемента, поэтому вместимость перебирается слева направо (в прямом порядке).

Вспомните, что в задаче о рюкзаке 0/1 мы перебирали вместимость справа налево, чтобы не допустить повторного использования элементов. В неограниченном рюкзаке поступают наоборот: перебирают слева направо. При вычислении dp[c] значение dp[c-w] уже обновлено в текущем проходе — это означает, что элемент i уже мог быть включён. Именно этого мы и хотим: элемент i можно снова добавить в решение, которое уже содержит элемент i.

Задача о монетах II формулируется так: по данным номиналам монет и сумме нужно подсчитать количество различных способов получить эту сумму (каждую монету можно использовать неограниченное число раз). Это вариант неограниченного рюкзака, в котором вместо максимизации ценности мы подсчитываем комбинации (combinations). Определим dp[c] как количество способов получить сумму c. Базовый случай: dp[0] = 1 (существует один способ получить 0: ничего не брать).

Для каждой монеты перебирайте суммы слева направо и накапливайте результат: dp[c] += dp[c - coin]. Базовый случай dp[0] = 1 задаёт начальное количество способов. Обратите внимание: внешний цикл проходит по монетам, а внутренний — по суммам. Благодаря этому естественным образом подсчитываются комбинации (combinations), а не перестановки (permutations), поскольку каждый номинал монеты рассматривается ровно один раз во внешнем проходе.

Порядок циклов имеет критическое значение. Если во внешнем цикле перебирать сумму, а во внутреннем — номинал монеты, мы подсчитываем перестановки (permutations), где порядок важен. Для amount=5 с монетами [1,2] варианты 1+2+2 и 2+1+2 считаются отдельно. Если во внешнем цикле перебирать номиналы монет, мы подсчитываем комбинации (combinations), где порядок не важен: 1+2+2 и 2+1+2 считаются одним и тем же вариантом. В задаче о монетах II требуется подсчитывать комбинации, поэтому номиналы монет находятся во внешнем цикле.

Ещё одна классическая задача о неограниченном рюкзаке: дан стержень длины n и цены для каждой длины стержня от 1 до n. Нужно найти максимальную выручку, оптимально распилив стержень. Каждый отрезок длины l можно продать по цене price[l], а отрезки можно использовать повторно (стержень можно распилить на несколько частей одинаковой длины). Это напрямую сводится к задаче о неограниченном рюкзаке, где W = n, а элементами являются различные длины отрезков.

Задача о монетах I — это другая задача, в которой требуется найти минимальное количество монет для получения целевой суммы. Здесь dp[c] = минимальное количество монет для получения суммы c. Рекуррентное соотношение: dp[c] = min(dp[c], dp[c - coin] + 1). Инициализируйте все элементы значением inf, кроме dp[0] = 0. Это также задача о неограниченном рюкзаке (монеты можно использовать повторно), поэтому суммы перебираются слева направо. Верните dp[amount], если значение конечно, иначе верните -1.

В трёх вариантах задачи о неограниченном рюкзаке используются разные операции над dp[c-coin]: максимизировать ценность: dp[c] = max(dp[c], dp[c-w] + v); инициализировать нулём. минимизировать стоимость: dp[c] = min(dp[c], dp[c-coin] + 1); инициализировать значением inf, dp[0]=0. подсчитывать количество способов: dp[c] += dp[c-coin]; инициализировать нулём, dp[0]=1. Распознать, какой вариант перед Вами, — это половина успеха в задачах на собеседованиях.

Все варианты задачи о неограниченном рюкзаке работают за O(n × W) времени и O(W) памяти, где n — количество типов элементов, а W — целевая сумма. В задачах о монетах n — это количество номиналов монет. На собеседовании назовите вариант (максимум, минимум или количество), запишите одномерный DP и чётко укажите, во внешнем цикле перебираются монеты или сумма: интервьюеры знают, что это различие проверяет глубокое понимание DP.

Используйте следующие признаки, чтобы определить подходящий вариант: неограниченное повторное использование → неограниченный рюкзак (перебор слева направо); каждый элемент используется ровно один раз → рюкзак 0/1 (перебор справа налево); в условии сказано «любое количество раз», «неограниченный запас» или «повторное использование разрешено» → неограниченный рюкзак. Примеры: задача о монетах, задача о распиле стержня, разбиение целого числа — всё это задачи о неограниченном рюкзаке. Задача о сумме подмножества, разбиение и рюкзак 0/1 — задачи 0/1. Ошибка в этом выборе приводит к неправильным ответам, которые трудно отлаживать.

Разбиение целого числа (LeetCode 343): разделите целое число n на как минимум 2 положительных целых числа так, чтобы максимизировать их произведение. Это задача о неограниченном рюкзаке, где «элементами» являются целые числа от 2 до n-1. Определим dp[i] = максимальное произведение целых чисел, сумма которых равна i. Для каждого элемента j от 2 до i: dp[i] = max(dp[i], max(j, dp[j]) * max(i-j, dp[i-j])). Этот пример показывает, как шаблон неограниченного рюкзака обобщается за пределы задач о монетах.

Проверьте, насколько Вы усвоили понятия из курса «Структуры данных & алгоритмы — подготовка к собеседованию» по этой теме.

В этом уроке Вы узнали: в неограниченном рюкзаке вместимость перебирается слева направо, чтобы разрешить повторное использование элементов, задача о монетах II подсчитывает комбинации (combinations), помещая монету во внешний цикл, и три варианта — максимизация, минимизация и подсчёт — различаются только операцией DP и инициализацией. Далее мы используем рюкзак 0/1 для решения задачи о разбиении на подмножества с равными суммами.