• API
• FAQ
• Tools
• Trends
• Archive
SHARE
TWEET

# The Coin Change Problem

a guest Mar 20th, 2017 2 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include <iostream>
2. using namespace std;
3.
4. int main () {
5.     /*
6.     First, we define 'n' as the target coin sum and 'm'
7.     as the number of coin denominations.
8.     */
9.     long long n, m;
10.     cin >> n >> m;
11.
12.     /*
13.     Here, we take all of the coin denominations from the input.
14.     */
15.     long long coins[m];
16.     for (long long i = 0; i < m; i++) {
17.         cin >> coins[i];
18.     }
19.
20.     /*
21.     Now, we declare the table of values, with
22.     m rows (one for each coin denomination) and
23.     n+1 columns (one for several sum from 0 to n).
24.     We then initialise the values of each cell in
25.     this table, with every value in the first column
26.     being initialised to 1, and every other value being
27.     initialised to 0.
28.     */
29.     long long table [m][n+1];
30.
31.     for (int i = 0; i < m; i++) {
32.         for (int j = 0; j < n+1; j++) {
33.             table[i][j] = ((j == 0) ? 1 : 0);
34.         }
35.     }
36.
37.     /*
38.     In this loop, we find the sum values which
39.     can be made using groups of the lowest-valued coin
40.     denomination.
41.     */
42.     for (int i = 0; i < n+1; i++) {
43.         if (i % coins[0] == 0)
44.             table[0][i] = 1;
45.     }
46.
47.     /*
48.     This loop builds the rest of the table - it
49.     uses the algorithm described earlier in the post.
50.     If the current coin denomination is smaller than
51.     the sum which we want to make, we set the value of
52.     the current cell to the sum of the number of ways
53.     to make the desired sum using the previous coin denominations
54.     and the number of ways to make the value (sum-m) using
55.     both the previous coin denomination and the current
56.     coin denomination, where 'sum is the desired sum, and 'm'
57.     is the current coin denomination. On the other hand,
58.     if the current coin denomination is larger than the
59.     desired sum, it cannot be used in any possible sets,
60.     so we just set the value of the current cell to the value
61.     of the cell in the same column of the row above.
62.     */
63.     for (int i = 1; i < m; i++) {
64.         long long curDenomination = coins[i];
65.         for (long long targetSum = 1; targetSum < n+1; targetSum++) {
66.             if (targetSum >= curDenomination) {
67.                 table [i] [targetSum] = table[i-1][targetSum] +
68.                                     table[i][targetSum-curDenomination];
69.             } else {
70.                 table [i] [targetSum] = table[i-1][targetSum];
71.             }
72.         }
73.     }
74.
75.     /*
76.     Finally, we print out the value in the bottom right
77.     corner of the table (this is the number of ways to make
78.     the full sum of n using all of the possible coin denominations).
79.     */
80.     cout << table [m-1][n];
81.     return 0;
82. }
RAW Paste Data
Top