Смена монеты | ДП-7

01.01.2020Динамическое программирование, Жадный алгоритм, Математика

При заданном значении 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.

1) Оптимальная субструктура
Чтобы подсчитать общее количество решений, мы можем разделить все наборы решений на два набора.
1) Растворы, не содержащие mth монеты (или Sm).
2) Растворы, содержащие хотя бы один Sm.
Пусть count (S [], m, n) будет функцией подсчета количества решений, тогда ее можно записать в виде суммы count (S [], m-1, n) и count (S [], m, п-Sm).

Следовательно, задача обладает оптимальным свойством субструктуры, поскольку проблема может быть решена с использованием решений подзадач.

2) Перекрывающиеся подзадачи
Ниже приводится простая рекурсивная реализация проблемы изменения монет. Реализация просто следует рекурсивной структуре, упомянутой выше.

C ++

// Рекурсивная программа на C для
// проблема смены монет.
#include<stdio.h>

// Возвращает количество способов, которыми мы можем
// сумма S [0 ... m-1] монет, чтобы получить сумму n

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

{

// Если n равно 0, то есть 1 решение

// (не включайте ни одной монеты)

if (n == 0)

return 1;

// Если n меньше 0, то нет

// решение существует

if (n < 0)

return 0;

// Если нет монет и п

// больше 0, то нет

// решение существует

if (m <=0 && n >= 1)

return 0;

// count - сумма решений (i)

// включая S [m-1] (ii) исключая S [m-1]

return count( S, m - 1, n ) + count( S, m, n-S[m-1] );

}

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

int main()

{

int i, j;

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

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

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

getchar();

return 0;

}

Джава

// Рекурсивная Java-программа для
// проблема смены монет.

import java.io.*;

class GFG {

// Возвращает количество способов, которыми мы можем

// сумма S [0 ... m-1] монет, чтобы получить сумму n

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

{

// Если n равно 0, то есть 1 решение

// (не включайте ни одной монеты)

if (n == 0)

return 1;

// Если n меньше 0, то нет

// решение существует

if (n < 0)

return 0;

// Если нет монет и п

// больше 0, то нет

// решение существует

if (m <=0 && n >= 1)

return 0;

// count - сумма решений (i)

// включая S [m-1] (ii) исключая S [m-1]

return count( S, m - 1, n ) +

count( S, m, n-S[m-1] );

}

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

public static void main(String[] args)

{

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

int m = arr.length;

System.out.println( count(arr, m, 4));

}

// Эта статья предоставлена vt_m.

python3

# Рекурсивная программа Python3 для
# проблема смены монет.

# Возвращает количество способов суммирования
# S [0 ... m-1] монет, чтобы получить сумму n

def count(S, m, n ):

# Если n равно 0, то есть 1

# решение (не включая монеты)

if (n == 0):

return 1

# Если n меньше 0, то нет

# решение существует

if (n < 0):

return 0;

# Если нет монет и н

# больше 0, то нет

# решение существует

if (m <=0 and n >= 1):

return 0

# count - сумма решений (i)

# включая S [m-1] (ii) исключая S [m-1]

return count( S, m - 1, n ) + count( S, m, n-S[m-1] );

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

arr = [1, 2, 3]

m = len(arr)

print(count(arr, m, 4))

# Этот код предоставлен Смитой Динеш Семвал

C #

// Рекурсивная программа на C # для
// проблема смены монет.

using System;

class GFG

{

// Возвращает количество способов, которыми мы можем

// сумма S [0 ... m-1] монет, чтобы получить сумму n

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

{

// Если n равно 0, то есть 1 решение

// (не включайте ни одной монеты)

if (n == 0)

return 1;

// Если n меньше 0, то нет

// решение существует

if (n < 0)

return 0;

// Если нет монет и п

// больше 0, то нет

// решение существует

if (m <=0 && n >= 1)

return 0;

// count - сумма решений (i)

// включая S [m-1] (ii) исключая S [m-1]

return count( S, m - 1, n ) +

count( S, m, n - S[m - 1] );

}

// Драйвер программы

public static void Main()

{

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

int m = arr.Length;

Console.Write( count(arr, m, 4));

}

}
// Этот код предоставлен Sam007

PHP

<?php
// Рекурсивная PHP-программа для
// проблема смены монет.

// Возвращает количество способов, которыми мы можем
// сумма S [0 ... m-1] монет, чтобы получить сумму n

function coun($S, $m, $n)

{

// Если n равно 0, то есть

// 1 решение (не включает

// любая монета)

if ($n == 0)

return 1;

// Если n меньше 0, то нет

// решение существует

if ($n < 0)

return 0;

// Если нет монет и п

// больше 0, то нет

// решение существует

if ($m <= 0 && $n >= 1)

return 0;

// count - сумма решений (i)

// включая S [m-1] (ii) исключая S [m-1]

return coun($S, $m - 1,$n ) +

coun($S, $m, $n - $S[$m - 1] );

}

// Код драйвера

$arr = array(1, 2, 3);

$m = count($arr);

echo coun($arr, $m, 4);

// Этот код предоставлен Sam007
?>

Выход :

Следует отметить, что вышеуказанная функция снова и снова вычисляет одни и те же подзадачи. Смотрите следующее дерево рекурсии для S = {1, 2, 3} и n = 5.
Функция C ({1}, 3) вызывается два раза. Если мы нарисуем полное дерево, то увидим, что существует множество подзадач, вызываемых более одного раза.

C() --> count()
                             C({1,2,3}, 5)                     
                           /             \    
                         /                 \                  
             C({1,2,3}, 2)                 C({1,2}, 5)
            /       \                      /      \         
           /         \                    /         \   
C({1,2,3}, -1)  C({1,2}, 2)        C({1,2}, 3)    C({1}, 5)
               /    \             /     \           /     \
             /       \           /       \         /        \
    C({1,2},0)  C({1},2)   C({1,2},1) C({1},3)    C({1}, 4)  C({}, 5)
                   / \     / \        /\         /     \         
                  /   \   /   \     /   \       /       \  
                .      .  .     .   .     .   C({1}, 3) C({}, 4)
                                               / \ 
                                              /   \   
                                             .      .

Поскольку те же самые подзадачи вызываются снова, эта проблема имеет свойство Перекрывающиеся подзадачи. Таким образом, проблема изменения монет имеет оба свойства (см. Это и это ) задачи динамического программирования. Как и другие типичные проблемы динамического программирования (DP) , повторных вычислений с одинаковыми подзадачами можно избежать, построив таблицу временных массивов [] [] по принципу «снизу вверх».

Решение для динамического программирования

C ++

// C ++ программа для задачи обмена монет.
#include<bits/stdc++.h>

using namespace std;

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;

cout << count(arr, m, n);

return 0;

}

// Этот код добавлен
// Аканкша Рай (Abby_akku)

// 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;

}

Джава

/ * Динамическое программирование Java-реализации Coin

Изменить проблему * /

import java.util.Arrays;

class CoinChange

{

static long countWays(int S[], int m, int n)

{

// Временная сложность этой функции: O (mn)

// Пространственная сложность этой функции: O (n)

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

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

// построен снизу вверх с использованием базы

// case (n = 0)

long[] table = new long[n+1];

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

Arrays.fill(table, 0); //На)

// Базовый случай (если задано значение 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];

}

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

public static void main(String args[])

{

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

int m = arr.length;

int n = 4;

System.out.println(countWays(arr, m, n));

}

}
// Этот код предоставлен Панкаджем Кумаром

питон

# Динамическое программирование Python для реализации Coin
# Изменить проблему

def count(S, m, n):

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

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

# case (n = 0)

table = [[0 for x in range(m)] for x in range(n+1)]

# Заполните записи для 0 значения регистра (n = 0)

for i in range(m):

table[0][i] = 1

# Заполните остальные записи таблицы снизу вверх

for i in range(1, n+1):

for j in range(m):

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

x = table[i - S[j]][j] if i-S[j] >= 0 else 0

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

y = table[i][j-1] if j >= 1 else 0

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

table[i][j] = x + y

return table[n][m-1]

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

arr = [1, 2, 3]

m = len(arr)

n = 4

print(count(arr, m, n))

# Этот код предоставлен Bhavya Jain

C #

/ * Динамическое программирование C # реализация Coin
Изменить проблему * /

using System;

class GFG

{

static long countWays(int []S, int m, int n)

{

// Временная сложность этой функции: O (mn)

// Пространственная сложность этой функции: O (n)

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

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

// построен снизу вверх с использованием базы

// case (n = 0)

int[] table = new int[n+1];

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

for(int i = 0; i < table.Length; i++)

{

table[i] = 0;

}

// Базовый случай (если задано значение 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];

}

// Функция драйвера

public static void Main()

{

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

int m = arr.Length;

int n = 4;

Console.Write(countWays(arr, m, n));

}

}
// Этот код предоставлен Sam007

PHP

<?php
// PHP программа для
// проблема смены монет.

function count1($S, $m, $n)

{

// Нам нужно n + 1 строк как

// таблица построена

// снизу вверх

// используя базовый случай 0

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

$table;

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

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

$table[$i][$j] = 0;

// Заполняем записи для

// 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];

}

// Код драйвера

$arr = array(1, 2, 3);

$m = count($arr);

$n = 4;

echo count1($arr, $m, $n);

// Этот код предоставлен mits
?>

Выход:

Сложность времени: 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];

}

Джава

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

{

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

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

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

int table[]=new int[n+1];

// Базовый случай (если задано значение 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];

}

питон

# Динамическое программирование Python для реализации Coin
# Изменить проблему

def count(S, m, n):

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

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

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

# Инициализировать все значения таблицы как 0

table = [0 for k in range(n+1)]

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

table[0] = 1

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

# после индекса больше или равно значению

# выбранная монета

for i in range(0,m):

for j in range(S[i],n+1):

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

return table[n]

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

arr = [1, 2, 3]

m = len(arr)

n = 4

x = count(arr, m, n)

print (x)

# Этот код предоставлен Афзалом Ансари

C #

// Динамическое программирование C # реализация
// проблемы изменения монеты

using System;

class GFG

{

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

{

// таблица [i] будет хранить

// количество решений для значения i.

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

// построен снизу вверх

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

int [] table = new int[n + 1];

// Базовый случай (если задано значение 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];

}

// Код драйвера

public static void Main()

{

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

int m = arr.Length;

int n = 4;

Console.Write(count(arr, m, n));

}
}

// Этот код предоставлен Раджем

PHP

<?php

function count_1( &$S, $m, $n )

{

// таблица [i] будет хранить номер

// решений для значения i. Нам нужно n + 1

// строки как таблица построена в

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

$table = array_fill(0, $n + 1, NULl);

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

$table[0] = 1;

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

// значения таблицы [] после индекса

// больше или равно значению

// выбранной монеты

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

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

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

return $table[$n];

}

// Код драйвера

$arr = array(1, 2, 3);

$m = sizeof($arr);

$n = 4;

$x = count_1($arr, $m, $n);

echo $x;

// Этот код добавлен
// ChitraNayal
?>

Выход:

Спасибо Рохану Лайшраму за предложение оптимизированной версии.

Ниже приводится упрощенная версия

// Напишите здесь код CPP

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

{

// нам нужна двумерная матрица для хранения результата

int table[m+1][n+1];

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

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

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

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

{table[0][i] = 1;

}

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

{

for(int j=1;j<=n;j++)

{

if(S[i-1]>j)

{

table[i][j]=table[i-1][j];

}

else

{

table[i][j]=table[i-1][j]+table[i][j-(i-1)];

}

return table[m][n];

}

Выход:

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Ссылки:
http://www.algorithmist.com/index.php/Coin_Change

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

Смена монеты | ДП-7

0.00 (0%) 0 votes