Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- using namespace std;
- int main () {
- /*
- First, we define 'n' as the target coin sum and 'm'
- as the number of coin denominations.
- */
- long long n, m;
- cin >> n >> m;
- /*
- Here, we take all of the coin denominations from the input.
- */
- long long coins[m];
- for (long long i = 0; i < m; i++) {
- cin >> coins[i];
- }
- /*
- Now, we declare the table of values, with
- m rows (one for each coin denomination) and
- n+1 columns (one for several sum from 0 to n).
- We then initialise the values of each cell in
- this table, with every value in the first column
- being initialised to 1, and every other value being
- initialised to 0.
- */
- long long table [m][n+1];
- for (int i = 0; i < m; i++) {
- for (int j = 0; j < n+1; j++) {
- table[i][j] = ((j == 0) ? 1 : 0);
- }
- }
- /*
- In this loop, we find the sum values which
- can be made using groups of the lowest-valued coin
- denomination.
- */
- for (int i = 0; i < n+1; i++) {
- if (i % coins[0] == 0)
- table[0][i] = 1;
- }
- /*
- This loop builds the rest of the table - it
- uses the algorithm described earlier in the post.
- If the current coin denomination is smaller than
- the sum which we want to make, we set the value of
- the current cell to the sum of the number of ways
- to make the desired sum using the previous coin denominations
- and the number of ways to make the value (sum-m) using
- both the previous coin denomination and the current
- coin denomination, where 'sum is the desired sum, and 'm'
- is the current coin denomination. On the other hand,
- if the current coin denomination is larger than the
- desired sum, it cannot be used in any possible sets,
- so we just set the value of the current cell to the value
- of the cell in the same column of the row above.
- */
- for (int i = 1; i < m; i++) {
- long long curDenomination = coins[i];
- for (long long targetSum = 1; targetSum < n+1; targetSum++) {
- if (targetSum >= curDenomination) {
- table [i] [targetSum] = table[i-1][targetSum] +
- table[i][targetSum-curDenomination];
- } else {
- table [i] [targetSum] = table[i-1][targetSum];
- }
- }
- }
- /*
- Finally, we print out the value in the bottom right
- corner of the table (this is the number of ways to make
- the full sum of n using all of the possible coin denominations).
- */
- cout << table [m-1][n];
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement