pad.mattdiesel.co.uk

Snippet - Change Combinations

Change Combinations (C++)

Calculates the number of combinations of coins to make an amount
Created 2015-01-19 21:05:06.762680 by Matt.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <iostream>
#include <map>
#include <array>

const std::array<int, 8> coins = {1, 2, 5, 10, 20, 50, 100, 200};
std::map<std::pair<int, int>, int> solved;

int ways(int C, int max = 7);

int ways(int C, int max)
{
    int ret = 0;

    // Only one way to make 1p or 0p
    if (C == 1 || max == 0) {
        return ( 1 );
    }
    else if (C == 0) {
        return ( 1 );
    }
    else if (max == 1) {
        // Only using 1p and 2p, there are floor(n/2)+1 combinations.
        return ( (C >> 1) + 1 );
    }

    // Check already calculated values
    auto search = solved.find({C, max});
    if (search != solved.end()) {
        return search->second;
    }

    // Cannot use coins higher than value.
    int i = max;
    while (coins[i] > C) {
        --i;
    }

    // Use all smaller denominations.
    for (; i >= 0; --i) {
        ret += ways(C - coins[i], i);
    }

    // Add to known solutions.
    solved[{C, max}] = ret;

    // If max is greater than the amount, then smaller
    // larger denominations also have the same combinations.
    // (e.g. C=20p, max=200p is the same as C=20p, max=100p)
    while (coins[--max] > C) {
        solved[{C, max}] = ret;
    }

    return ret;
}


int main(int argc, char const *argv[])
{
    int x;
    std::cin >> x;

    std::cout << ways(x) << std::endl;

    return 0;
}