Advertisement
Guest User

The Coin Change Problem

a guest
Mar 20th, 2017
22
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.48 KB | None | 0 0
  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. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement