Все возможные комбинации монет

Question

Мне нужно написать программу, которая отображает все возможные комбинации комбинаций, учитывая массив наименований [1, 2, 5, 10, 20, 50, 100, 200] // 1 = 1 цент

Value, чтобы сделать переход от = 300

Я основывая свой код на решение с этого сайта http://www.geeksforgeeks.org/dynamic-programming-set-7-coin-change/

#include<stdio.h> 

int count(int S[], int m, int n) 
{ 
    int i, j, x, y; 

    // We need n+1 rows as the table is consturcted in bottom up manner using 
    // the base case 0 value case (n = 0) 
    int table[n+1][m]; 

    // Fill the enteries for 0 value case (n = 0) 
    for (i=0; i<m; i++) 
     table[0][i] = 1; 

    // Fill rest of the table enteries in bottom up manner 
    for (i = 1; i < n+1; i++) 
    { 
     for (j = 0; j < m; j++) 
     { 
      // Count of solutions including S[j] 
      x = (i-S[j] >= 0)? table[i - S[j]][j]: 0; 

      // Count of solutions excluding S[j] 
      y = (j >= 1)? table[i][j-1]: 0; 

      // total count 
      table[i][j] = x + y; 
     } 
    } 
    return table[n][m-1]; 
} 

// Driver program to test above function 
int main() 
{ 
    int arr[] = {1, 2, 5, 10, 20, 50, 100, 200}; //coins array 
    int m = sizeof(arr)/sizeof(arr[0]); 
    int n = 300; //value to make change from 
    printf(" %d ", count(arr, m, n)); 
    return 0; 
} 

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

1 цента: n количество возможных комбинаций.

2 цента:

5 центов:

и так далее ...

Как я могу изменить код для достижения этой цели?

Answer 1

Жадный алгоритм подход

есть этот деноминации в качестве Int массива говорят, Int ден [] = [1, 2, 5, 10, 20, 50, 100, 200]

перебирать этот массив

Для каждой итерации необходимо выполнить следующие действия

Возьмите элемент в массиве деноминаций

Разделите изменение, которое будет выделено номером, на номер массива номиналов

Если число, выделенное изменением, отлично делится на число в массиве номиналов, то вы закончите с изменением для этого числа.

Если число не идеально делится затем проверить на остаток и сделать то же итерации с другим номером

Выход внутренней итерации, как только вы получаете значение, равное числу изменений

сделать то же самое для следующее деноминация, доступная в нашем массиве деноминации.

---

Explained with example 
den = [1 , 2, 5, 10, 20, 50, 100, 200] 
Change to be alloted : 270, let take this as x 
and y be the temporary variable 
Change map z[coin denomination, count of coins] 

int y, z[]; 
First iteration : 
den = 1 
x = 270 
y = 270/1; 
if x is equal to y*den 
then z[den, y] // z[1, 270] 
Iteration completed 

Second Iteration: 
den = 2 
x = 270 
y = 270/2; 
if x is equal to y*den 
then z[den , y] // [2, 135] 
Iteration completed 

Lets take a odd number 
x = 217 and den = 20 
y= 217/20; 
now x is not equal to y*den 
then update z[den, y] // [20, 10] 
find new x = x - den*y = 17 
x=17 and identify the next change value by greedy it would be 10 
den = 10 
y = 17/10 
now x is not equal to y*den 
then update z[den, y] // [10, 1] 
find new x = x - den*y = 7 

then do the same and your map would be having following entries 
[20, 10] 
[10, 1] 
[5, 1] 
[2, 1]