dynamic-programming
Проблема с изменением монеты

Количество способов получить общее количество

Учитывая монеты разных номиналов и общее количество, сколько способов мы можем объединить эти монеты, чтобы получить общее количество? Предположим, что у нас есть coins = {1, 2, 3} и total = 5 , мы можем получить общее количество 5 способами:

• 1 1 1 1 1
• 1 1 1 2
• 1 1 3
• 1 2 2
• 2 3

Проблема тесно связана с проблемой ранца. Единственное различие заключается в том, что у нас есть неограниченный запас монет. Мы будем использовать динамическое программирование для решения этой проблемы.

Мы будем использовать 2D-массив dp [n] [total + 1], где n - количество разных номиналов монет, которые у нас есть. Для нашего примера нам понадобится dp [3] [6] . Здесь dp [i] [j] будет обозначать количество способов, которыми мы можем получить j, если бы у нас были монеты с монетами [0] до монет [i] . Например, dp [1] [2] будет хранить, если бы у нас были монеты [0] и монеты [1] , сколько способов мы могли бы сделать 2 . Давай начнем:

Для dp [0] [0] мы спрашиваем себя, было ли у нас только 1 деноминация монеты, то есть монеты [0] = 1 , сколько способов мы можем получить 0 ? Ответ один путь, а это если мы вообще не возьмем монету. Двигаясь дальше, dp [0] [1] будет представлять, если бы у нас были только монеты [0] , сколько способов можно получить 1 ? Ответ снова 1 . Точно так же dp [0] [2] , dp [0] [3] , dp [0] [4] , dp [0] [5] будут равны 1 . Наш массив будет выглядеть так:

     +---+---+---+---+---+---+---+
(den)|   | 0 | 1 | 2 | 3 | 4 | 5 |
     +---+---+---+---+---+---+---+
 (1) | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
     +---+---+---+---+---+---+---+
 (2) | 1 |   |   |   |   |   |   |
     +---+---+---+---+---+---+---+
 (3) | 2 |   |   |   |   |   |   |
     +---+---+---+---+---+---+---+

Для dp [1] [0] мы спрашиваем себя, были ли у нас монеты из двух деноминаций, то есть, если бы у нас были монеты [0] = 1 и монеты [1] = 2 , сколько способов мы могли бы сделать 0 ? Ответ равен 1 , а это значит, что вообще нет монет. Для dp [1] [1] , поскольку монеты [1] = 2 больше нашего текущего количества, 2 не будет способствовать получению общего. Таким образом, мы исключим 2 и подсчитаем количество способов, которыми мы можем получить общее использование монет [0] . Но это значение уже сохраняется в dp [0] [1] ! Поэтому мы возьмем значение сверху. Наша первая формула:

if coins[i] > j
    dp[i][j] := dp[i-1][j]
end if

Для dp [1] [2] , сколько способов мы можем получить 2 , если бы у нас были монеты номинала 1 и 2 ? Мы можем сделать 2, используя монеты номинала 1 , которые представлены dp [0] [2] , снова мы можем взять 1 деноминацию 2, которая хранится в dp [1] [2-монеты [i]] , где i = 1 . Зачем? Это будет очевидно, если мы посмотрим на следующий пример. Для dp [1] [3] , сколько способов мы можем получить 3 , если бы у нас были монеты номинала 1 и 2 ? Мы можем сделать 3, используя монеты номинала 1 одним способом, который хранится в dp [0] [3] . Теперь, если мы возьмем 1 деноминацию 2 , нам понадобится 3 - 2 = 1, чтобы получить общее количество. Количество способов получить 1 с использованием монет номинала 1 и 2 хранится в dp [1] [1] , которое может быть записано как: dp [i] [j-coins [i]] , где i = 1 . Вот почему мы написали предыдущее значение таким образом. Наша вторая и последняя формула будет:

if coins[i] <= j
    dp[i][j] := dp[i-1][j] + dp[i][j-coins[i]]
end if

Это две необходимые формулы для заполнения всего массива dp . После заполнения массив будет выглядеть так:

     +---+---+---+---+---+---+---+
(den)|   | 0 | 1 | 2 | 3 | 4 | 5 |
     +---+---+---+---+---+---+---+
 (1) | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
     +---+---+---+---+---+---+---+
 (2) | 1 | 1 | 1 | 2 | 2 | 3 | 3 |
     +---+---+---+---+---+---+---+
 (3) | 2 | 1 | 1 | 2 | 3 | 4 | 5 |
     +---+---+---+---+---+---+---+

dp [2] [5] будет содержать наш требуемый ответ. Алгоритм:

Procedure CoinChange(coins, total):
n := coins.length
dp[n][total + 1]
for i from 0 to n
    dp[i][0] := 1
end for
for i from 0 to n
    for j from 1 to (total + 1)
        if coins[i] > j
            dp[i][j] := dp[i-1][j]
        else
            dp[i][j] := dp[i-1][j] + dp[i][j-coins[i]]
        end if
    end for
end for
Return dp[n-1][total]

Сложность времени этого алгоритма равна O(n * total) , где n - количество достоинств монет, которые мы имеем.

Минимальное количество монет для получения всего

Учитывая монеты разных номиналов и общую сумму, сколько монет нужно объединить, чтобы получить общее количество, если мы используем минимальное количество монет? Предположим, что у нас есть coins = {1, 5, 6, 8} и total = 11 , мы можем получить общее количество, используя 2 монеты, которые являются {5, 6} . Это действительно минимальное количество монет, необходимых для получения 11 . Мы также предположим, что существует неограниченная поставка монет. Мы будем использовать динамическое программирование для решения этой проблемы.

Мы будем использовать 2D-массив dp [n] [total + 1], где n - количество разных номиналов монет, которые у нас есть. Для нашего примера нам понадобится dp [4] [12] . Здесь dp [i] [j] будет обозначать минимальное количество монет, необходимых для получения j, если бы у нас были монеты с монетами [0] до монет [i] . Например, dp [1] [2] будет хранить, если бы у нас были монеты [0] и монеты [1] , каково минимальное количество монет, которые мы можем использовать для создания 2 . Давай начнем:

Сначала для 0- го столбца можно сделать 0 , не беря вообще никаких монет. Таким образом, все значения 0- го столбца будут равны 0 . Для dp [0] [1] мы спрашиваем себя, было ли у нас только 1 деноминация монеты, то есть монеты [0] = 1 , каково минимальное количество монет, необходимых для получения 1 ? Ответ: 1 . Для dp [0] [2] , если у нас было только 1 , каково минимальное количество монет, необходимых для получения 2 . Ответ: 2 . Аналогично dp [0] [3] = 3 , dp [0] [4] = 4 и т. Д. Здесь стоит упомянуть, что если бы у нас не было монеты номинала 1 , могли бы быть случаи, когда сумма не может быть достигнута только с использованием одной монеты. Для простоты возьмем 1 в нашем примере. После первой итерации наш массив dp будет выглядеть так:

        +---+---+---+---+---+---+---+---+---+---+---+---+---+
 (denom)|   | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10| 11|
        +---+---+---+---+---+---+---+---+---+---+---+---+---+
    (1) | 0 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10| 11|
        +---+---+---+---+---+---+---+---+---+---+---+---+---+
    (5) | 1 | 0 |   |   |   |   |   |   |   |   |   |   |   |
        +---+---+---+---+---+---+---+---+---+---+---+---+---+
    (6) | 2 | 0 |   |   |   |   |   |   |   |   |   |   |   |
        +---+---+---+---+---+---+---+---+---+---+---+---+---+
    (8) | 3 | 0 |   |   |   |   |   |   |   |   |   |   |   |
        +---+---+---+---+---+---+---+---+---+---+---+---+---+

Двигаясь дальше, для dp [1] [1] , мы спрашиваем себя, были ли у нас монеты [0] = 1 и монеты [1] = 5 , каково минимальное количество монет, необходимых для получения 1 ? Поскольку монеты [1] больше нашей текущей суммы, это не повлияет на наши расчеты. Нам нужно будет исключить монеты [5] и получить 1, используя только монеты [0] . Это значение сохраняется в dp [0] [1] . Поэтому мы берем значение сверху. Наша первая формула:

if coins[i] > j
    dp[i][j] := dp[i-1][j]

Это условие будет истинным до тех пор, пока наша сумма не будет равна 5 в dp [1] [5]. В этом случае мы можем сделать 5 двумя способами:

• Мы берем 5 наименований монет [0] , которые хранятся на dp [0] [5] (сверху).
• Мы принимаем 1 деноминацию монет [1] и ( 5 - 5 ) = 0 наименований монет [0] .

Мы выберем минимум этих двух. Таким образом, dp [1] [5] = min ( dp [0] [5] , 1 + dp [1] [0] ) = 1 . Почему мы упоминали, что 0 номиналов монет [0] здесь будут очевидны в нашей следующей позиции.

Для dp [1] [6] мы можем сделать 6 двумя способами:

• Мы берем 6 наименований монет [0] , которые хранятся сверху.
• Мы можем взять 1 деноминацию 5 , нам понадобится 6 - 5 = 1, чтобы получить общее количество. Минимальное количество способов получения 1 с использованием монет номинала 1 и 5 сохраняется в dp [1] [1] , которое может быть записано как dp [i] [j-coins [i]] , где i = 1 . Вот почему мы таким образом написали предыдущее значение.

Мы возьмем минимум этих двух способов. Итак, наша вторая формула будет:

if coins[i] >= j
    dp[i][j] := min(dp[i-1][j], dp[i][j-coins[i]])

Используя эти две формулы, мы можем заполнить всю таблицу. Наш конечный результат будет:

        +---+---+---+---+---+---+---+---+---+---+---+---+---+
 (denom)|   | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10| 11|
        +---+---+---+---+---+---+---+---+---+---+---+---+---+
    (1) | 0 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10| 11|
        +---+---+---+---+---+---+---+---+---+---+---+---+---+
    (5) | 1 | 0 | 1 | 2 | 3 | 4 | 1 | 2 | 3 | 4 | 5 | 2 | 3 |
        +---+---+---+---+---+---+---+---+---+---+---+---+---+
    (6) | 2 | 0 | 1 | 2 | 3 | 4 | 1 | 1 | 2 | 3 | 4 | 2 | 2 |
        +---+---+---+---+---+---+---+---+---+---+---+---+---+
    (8) | 3 | 0 | 1 | 2 | 3 | 4 | 1 | 1 | 2 | 1 | 2 | 2 | 2 |
        +---+---+---+---+---+---+---+---+---+---+---+---+---+

Наш требуемый результат будет сохранен в dp [3] [11] . Процедура будет:

Procedure coinChange(coins, total):
n := coins.length
dp[n][total + 1]
for i from 0 to n
    dp[i][0] := 0
end for
for i from 1 to (total + 1)
    dp[0][i] := i
end for
for i from 1 to n
    for j from 1 to (total + 1)
        if coins[i] > j
            dp[i][j] := dp[i-1][j] 
        else
            dp[i][j] := min(dp[i-1][j], dp[i][j-coins[i]])
        end if
    end for
end for
Return dp[n-1][total]

Сложность выполнения этого алгоритма: O (n * total), где n - количество наименований монет.

Чтобы распечатать необходимые монеты, нам нужно проверить:

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

Алгоритм:

Procedure printChange(coins, dp, total):
i := coins.length - 1
j := total
min := dp[i][j]
while j is not equal to 0
    if dp[i-1][j] is equal to min
        i := i - 1
    else
        Print(coins[i])
        j := j - coins[i]
    end if
end while

Для нашего примера направление будет:

Значения будут 6 , 5 .