Задача о полном рюкзаке¶

В этом разделе сначала решим еще одну распространенную задачу о рюкзаке - задачу о полном рюкзаке, а затем рассмотрим один из ее типичных частных случаев: задачу о размене монет.

Задача о полном рюкзаке¶

Question

Даны \(n\) предметов. Вес \(i\)-го предмета равен \(wgt[i-1]\) , стоимость равна \(val[i-1]\) . Также дан рюкзак вместимости \(cap\) . Каждый предмет можно выбирать многократно. Найдите максимальную суммарную стоимость, которую можно поместить в рюкзак при заданной вместимости. Пример показан на рисунке ниже.

Идея динамического программирования¶

Задача о полном рюкзаке очень похожа на задачу о рюкзаке 0-1. Разница состоит только в том, что количество выборов каждого предмета не ограничено.

В задаче о рюкзаке 0-1 каждого предмета существует только один экземпляр, поэтому после того как предмет \(i\) помещен в рюкзак, выбирать можно только из первых \(i-1\) предметов.
В задаче о полном рюкзаке количество предметов не ограничено, поэтому после того как предмет \(i\) помещен в рюкзак, можно продолжать выбирать из первых \(i\) предметов.

При этом состояние \([i, c]\) в задаче о полном рюкзаке может изменяться двумя способами.

Не брать предмет \(i\) : как и в задаче о рюкзаке 0-1, переход осуществляется в \([i-1, c]\) .
Взять предмет \(i\) : в отличие от рюкзака 0-1 переход происходит в \([i, c-wgt[i-1]]\) .

Следовательно, уравнение перехода состояния принимает вид:

\[ dp[i, c] = \max(dp[i-1, c], dp[i, c - wgt[i-1]] + val[i-1]) \]

Реализация кода¶

Если сравнить код этой задачи с кодом задачи о рюкзаке 0-1, то окажется, что в переходе состояний меняется только одна деталь: вместо \(i-1\) появляется \(i\). Все остальное остается таким же:

[file]{unbounded_knapsack}-[class]{}-[func]{unbounded_knapsack_dp}

Оптимизация пространства¶

Поскольку текущее состояние переходит из состояния слева и состояния сверху, после оптимизации памяти каждую строку таблицы \(dp\) нужно обходить слева направо.

Этот порядок обхода как раз противоположен задаче о рюкзаке 0-1. Эту разницу удобно понять, рассмотрев то, что показано на рисунке ниже.

Код реализации здесь довольно прост: достаточно просто убрать первое измерение массива dp :

[file]{unbounded_knapsack}-[class]{}-[func]{unbounded_knapsack_dp_comp}

Задача о размене монет¶

Задача о рюкзаке представляет собой целый класс задач динамического программирования, у которого есть множество вариантов, и одной из таких вариаций является задача о размене монет.

Question

Даны \(n\) видов монет, номинал монеты \(i\) равен \(coins[i - 1]\) , а целевая сумма равна \(amt\) . Монеты каждого вида можно брать многократно. Требуется найти минимальное число монет, которыми можно набрать целевую сумму. Если набрать сумму невозможно, верните \(-1\) . Пример показан на рисунке ниже.

Идея динамического программирования¶

Задачу о размене монет можно рассматривать как частный случай задачи о полном рюкзаке. Между ними существуют следующие соответствия и различия.

Эти две задачи можно взаимно преобразовать: «предмет» соответствует «монете», «вес предмета» соответствует «номиналу монеты», а «вместимость рюкзака» соответствует «целевой сумме».
Цель оптимизации противоположна: в задаче о полном рюкзаке нужно максимизировать стоимость предметов, а в задаче о размене монет - минимизировать число монет.
В задаче о полном рюкзаке ищется решение, не превышающее вместимость, а в задаче о размене монет требуется ровно набрать целевую сумму.

Шаг 1: продумать решения на каждом раунде, определить состояние и тем самым получить таблицу \(dp\)

Подзадача, соответствующая состоянию \([i, a]\) , выглядит так: минимальное число монет из первых \(i\) видов, которыми можно набрать сумму \(a\). Решение этой подзадачи обозначается как \(dp[i, a]\) .

Размер двумерной таблицы \(dp\) равен \((n+1) \times (amt+1)\) .

Шаг 2: найти оптимальную подструктуру и на ее основе вывести уравнение перехода состояния

По сравнению с задачей о полном рюкзаке здесь есть два отличия в уравнении перехода состояния.

Нужно искать минимум, а не максимум, поэтому оператор \(\max()\) заменяется на \(\min()\) .
Оптимизируемое значение - это число монет, а не суммарная стоимость, поэтому при выборе монеты нужно просто прибавить \(1\) .

\[ dp[i, a] = \min(dp[i-1, a], dp[i, a - coins[i-1]] + 1) \]

Шаг 3: определить граничные условия и порядок переходов

Когда целевая сумма равна \(0\) , минимальное число монет для ее набора равно \(0\) , то есть весь первый столбец \(dp[i, 0]\) заполняется нулями.

Когда монет нет, невозможно набрать никакую целевую сумму \(> 0\). Это и есть недопустимое решение. Чтобы функция \(\min()\) в уравнении перехода состояния могла распознавать и отбрасывать такие недопустимые решения, удобно использовать значение \(+ \infty\). То есть всю первую строку \(dp[0, a]\) нужно инициализировать значением \(+ \infty\) .

Реализация кода¶

Большинство языков программирования не предоставляет представление для \(+ \infty\) в целочисленном виде, поэтому обычно приходится заменять его на максимальное значение типа int . Но тогда возникает риск переполнения: операция \(+ 1\) в уравнении перехода может переполнить большое число.

Поэтому здесь мы используем число \(amt + 1\) как обозначение недопустимого решения, потому что для набора суммы \(amt\) максимум нужно не больше чем \(amt\) монет. Перед возвратом результата проверяем, равно ли \(dp[n, amt]\) значению \(amt + 1\). Если да, то возвращаем \(-1\) , что означает невозможность набрать целевую сумму. Код приведен ниже:

[file]{coin_change}-[class]{}-[func]{coin_change_dp}

Как показано на рисунке ниже, процесс динамического программирования для задачи о размене монет очень похож на задачу о полном рюкзаке.

Оптимизация пространства¶

Оптимизация пространства для задачи о размене монет выполняется так же, как и для полного рюкзака:

[file]{coin_change}-[class]{}-[func]{coin_change_dp_comp}

Задача о размене монет II¶

Question

Даны \(n\) видов монет, номинал монеты \(i\) равен \(coins[i - 1]\) , а целевая сумма равна \(amt\) . Монеты каждого вида можно брать многократно. Найдите число различных комбинаций монет, которыми можно набрать целевую сумму. Пример показан на рисунке ниже.

Идея динамического программирования¶

По сравнению с предыдущей задачей здесь целью является число комбинаций. Поэтому подзадача меняется на следующую: число комбинаций из первых \(i\) видов монет, которыми можно набрать сумму \(a\). При этом таблица \(dp\) по-прежнему остается двумерной матрицей размера \((n+1) \times (amt + 1)\) .

Число комбинаций для текущего состояния равно сумме числа комбинаций для двух решений: не брать текущую монету и брать текущую монету. Поэтому уравнение перехода состояния принимает вид:

\[ dp[i, a] = dp[i-1, a] + dp[i, a - coins[i-1]] \]

Когда целевая сумма равна \(0\) , ее можно набрать, не выбирая ни одной монеты, поэтому весь первый столбец \(dp[i, 0]\) нужно инициализировать единицами. Когда монет нет, невозможно набрать никакую сумму \(>0\) , поэтому вся первая строка \(dp[0, a]\) должна быть заполнена нулями.

Реализация кода¶

[file]{coin_change_ii}-[class]{}-[func]{coin_change_ii_dp}

Оптимизация пространства¶

При оптимизации памяти способ остается тем же самым: достаточно убрать измерение, отвечающее за виды монет:

[file]{coin_change_ii}-[class]{}-[func]{coin_change_ii_dp_comp}