Рубрики

Смена монет программы

При заданном значении N, если мы хотим внести изменения в N центов, и у нас есть бесконечный запас каждой из монет с достоинством S = {S1, S2, .., Sm}, сколько способов мы можем внести изменение? Порядок монет не имеет значения.

Например, для N = 4 и S = {1,2,3} существует четыре решения: {1,1,1,1}, {1,1,2}, {2,2}, {1, 3}. Таким образом, выходное значение должно быть 4. Для N = 10 и S = {2, 5, 3, 6} существует пять решений: {2,2,2,2,2}, {2,2,3,3}, {2,2,6}, {2,3,5} и {5,5}. Поэтому на выходе должно быть 5.

С

// C программа для замены монет.
#include<stdio.h>

  

int count( int S[], int m, int n )

{

    int i, j, x, y;

  

    // Нам нужно n + 1 строк для построения таблицы

    // снизу вверх, используя базовый случай 0

    // значение регистра (n = 0)

    int table[n+1][m];

     

    // Заполняем записи для случая с 0 значениями (n = 0)

    for (i=0; i<m; i++)

        table[0][i] = 1;

  

    // Заполняем остальные записи таблицы внизу

    // вверх

    for (i = 1; i < n+1; i++)

    {

        for (j = 0; j < m; j++)

        {

            // Количество решений, включая S [j]

            x = (i-S[j] >= 0)? table[i - S[j]][j]: 0;

  

            // Количество решений, исключая S [j]

            y = (j >= 1)? table[i][j-1]: 0;

  

            // общее количество

            table[i][j] = x + y;

        }

    }

    return table[n][m-1];

}

  
// Программа драйвера для проверки вышеуказанной функции

int main()

{

    int arr[] = {1, 2, 3};

    int m = sizeof(arr)/sizeof(arr[0]);

    int n = 4;

    printf(" %d ", count(arr, m, n));

    return 0;

}


Выход:

4

Сложность времени: O (мн)

Ниже приведен упрощенный вариант метода 2. Требуемое вспомогательное пространство здесь только O (n).

С

int count( int S[], int m, int n )

{

    // таблица [i] будет хранить количество решений для

    // значение i. Нам нужно n + 1 рядов, так как таблица построена

    // снизу вверх, используя базовый вариант (n = 0)

    int table[n+1];

  

    // Инициализируем все значения таблицы как 0

    memset(table, 0, sizeof(table));

  

    // Базовый случай (если задано значение 0)

    table[0] = 1;

  

    // Собираем все монеты одну за другой и обновляем значения таблицы []

    // после того, как индекс больше или равен значению

    // выбрал монету

    for(int i=0; i<m; i++)

        for(int j=S[i]; j<=n; j++)

            table[j] += table[j-S[i]];

  

    return table[n];

}

Пожалуйста, обратитесь к полной статье о динамическом программировании | Установите 7 (Смена монеты) для более подробной информации!

Рекомендуемые посты:

Смена монет программы

0.00 (0%) 0 votes