fork download
copy 
  1. #include <stdio.h>
  2.  
  3. #define N 50
  4. #define CHANGESIZE 4
  5.  
  6. int changeSize;
  7.  
  8. // Sum upto 50
  9. int table[N + 1][CHANGESIZE + 1];
  10.  
  11. // Returns the count of ways we can sum  S[0...m-1] coins to get sum n
  12. int count( int S[], int m, int n )
  13. {
  14.     // If n is 0 then there is 1 solution (do not include any coin)
  15.     if (n == 0)
  16.         return 1;
  17.  
  18.     // If n is less than 0 then no solution exists
  19.     if (n < 0)
  20.         return 0;
  21.  
  22.     // If there are no coins and n is greater than 0, then no solution exist
  23.     if (m <=0 && n >= 1)
  24.         return 0;
  25.  
  26.     // count is sum of solutions (i) including S[m-1] (ii) excluding S[m-1]
  27.     return count( S, m - 1, n ) + count( S, m, n-S[m-1] );
  28. }
  29.  
  30. int getchange(int n, int denom)
  31. {
  32.     int next_denom = 0;
  33.  
  34.     switch(denom) {
  35. 	case 25:
  36. 	next_denom = 10;
  37. 	break;
  38.  
  39. 	case 10:
  40. 	next_denom = 5;
  41. 	break;
  42.  
  43. 	case 5:
  44. 	next_denom = 1;
  45. 	break;
  46.  
  47. 	case 1:
  48. 	return 1;
  49.     }
  50.  
  51.     int ways = 0;
  52.     int i = 0;
  53.  
  54.     for (i = 0; i*denom <= n; i++) {
  55. 	ways += getchange(n - i*denom, next_denom);
  56.     }
  57.  
  58.     return ways;
  59. }
  60.  
  61. // Converted top down DP version of count()
  62. int countDP(int S[], int m, int n)
  63. {
  64.     if (n == 0) {
  65. 	table[n][m] = 1;
  66. 	return table[n][m];
  67.     }
  68.     if (n < 0) {
  69. 	return 0;
  70.     }
  71.  
  72.     if (m <=0 && n >= 1)
  73.         return 0;
  74.  
  75.     if (n-S[m-1] < 0) {
  76. 	return 0;
  77.     }
  78.  
  79.     if (table[n][m-1] == 0) {
  80. 	table[n][m-1] = countDP(S, m-1, n);
  81.     }
  82.  
  83.     if (table[n-S[m-1]][m] == 0) {
  84. 	table[n-S[m-1]][m] = countDP(S, m, n-S[m-1]);
  85.     }
  86.  
  87.     return (table[n][m-1] + table[n-S[m-1]][m]);
  88. }
  89.  
  90. void inittable()
  91. {
  92. 	int i = 0;
  93. 	int j = 0;
  94.  
  95.     for (i = 0; i < N + 1 ; i++) {
  96. 	for (j = 0; j < changeSize + 1; j++) {
  97. 	    table[i][j] = 0;
  98. 	}
  99.     }
  100.  
  101.     return;
  102. }
  103.  
  104. int main()
  105. {
  106.     int ways = 0;
  107.     int sum = 0;
  108.     int change[4] = {25, 10, 5, 1};
  109.     changeSize = sizeof(change)/sizeof(change[0]);
  110.  
  111.     for (sum = 1; sum < 50; sum++) {
  112. 	printf("Sum %d\n", sum);
  113. 	printf("Count = %d\n", count(change, changeSize, sum));
  114.  
  115. 	printf("GetChange = %d\n", getchange(sum, 25));
  116.  
  117. 	ways = countDP(change, changeSize, sum);
  118. 	printf("CountDP = %d\n", ways);
  119. 	printf("============\n\n");
  120.  
  121. 	inittable();
  122.     }
  123.  
  124.     return 0;
  125. }
  126.  
Success #stdin #stdout 0s 2248KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Sum 1
Count = 1
GetChange = 1
CountDP = 1
============

Sum 2
Count = 1
GetChange = 1
CountDP = 1
============

Sum 3
Count = 1
GetChange = 1
CountDP = 1
============

Sum 4
Count = 1
GetChange = 1
CountDP = 1
============

Sum 5
Count = 2
GetChange = 2
CountDP = 2
============

Sum 6
Count = 2
GetChange = 2
CountDP = 2
============

Sum 7
Count = 2
GetChange = 2
CountDP = 2
============

Sum 8
Count = 2
GetChange = 2
CountDP = 2
============

Sum 9
Count = 2
GetChange = 2
CountDP = 2
============

Sum 10
Count = 4
GetChange = 4
CountDP = 4
============

Sum 11
Count = 4
GetChange = 4
CountDP = 4
============

Sum 12
Count = 4
GetChange = 4
CountDP = 4
============

Sum 13
Count = 4
GetChange = 4
CountDP = 4
============

Sum 14
Count = 4
GetChange = 4
CountDP = 4
============

Sum 15
Count = 6
GetChange = 6
CountDP = 6
============

Sum 16
Count = 6
GetChange = 6
CountDP = 6
============

Sum 17
Count = 6
GetChange = 6
CountDP = 6
============

Sum 18
Count = 6
GetChange = 6
CountDP = 6
============

Sum 19
Count = 6
GetChange = 6
CountDP = 6
============

Sum 20
Count = 9
GetChange = 9
CountDP = 9
============

Sum 21
Count = 9
GetChange = 9
CountDP = 9
============

Sum 22
Count = 9
GetChange = 9
CountDP = 9
============

Sum 23
Count = 9
GetChange = 9
CountDP = 9
============

Sum 24
Count = 9
GetChange = 9
CountDP = 9
============

Sum 25
Count = 13
GetChange = 13
CountDP = 13
============

Sum 26
Count = 13
GetChange = 13
CountDP = 13
============

Sum 27
Count = 13
GetChange = 13
CountDP = 13
============

Sum 28
Count = 13
GetChange = 13
CountDP = 13
============

Sum 29
Count = 13
GetChange = 13
CountDP = 13
============

Sum 30
Count = 18
GetChange = 18
CountDP = 18
============

Sum 31
Count = 18
GetChange = 18
CountDP = 18
============

Sum 32
Count = 18
GetChange = 18
CountDP = 18
============

Sum 33
Count = 18
GetChange = 18
CountDP = 18
============

Sum 34
Count = 18
GetChange = 18
CountDP = 18
============

Sum 35
Count = 24
GetChange = 24
CountDP = 24
============

Sum 36
Count = 24
GetChange = 24
CountDP = 24
============

Sum 37
Count = 24
GetChange = 24
CountDP = 24
============

Sum 38
Count = 24
GetChange = 24
CountDP = 24
============

Sum 39
Count = 24
GetChange = 24
CountDP = 24
============

Sum 40
Count = 31
GetChange = 31
CountDP = 31
============

Sum 41
Count = 31
GetChange = 31
CountDP = 31
============

Sum 42
Count = 31
GetChange = 31
CountDP = 31
============

Sum 43
Count = 31
GetChange = 31
CountDP = 31
============

Sum 44
Count = 31
GetChange = 31
CountDP = 31
============

Sum 45
Count = 39
GetChange = 39
CountDP = 39
============

Sum 46
Count = 39
GetChange = 39
CountDP = 39
============

Sum 47
Count = 39
GetChange = 39
CountDP = 39
============

Sum 48
Count = 39
GetChange = 39
CountDP = 39
============

Sum 49
Count = 39
GetChange = 39
CountDP = 39
============
https://ideone.com/XN6v0F
Coin change - Total ways
language:
C (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!