Project Euler #31

Question

Problem Description:

In England the currency is made up of pound, £, and pence, p, and there are eight coins in general circulation:
1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p).
It is possible to make £2 in the following way:
1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p
How many different ways can £2 be made using any number of coins?

I've tried to come up with my own algorithm for this and failed. So, I came upon this one (the accepted answer). I've tried to replicate it in C++ here. When I enter 1, 2, and 5 into combos() in the main() function, it comes up with the right answer, but 10 returns 11, when it should be 12. What's wrong with my algorithm?

#include <iostream>
#include <cstdlib>
using namespace std;

int coin[] = {1, 2, 5, 10, 20, 50, 100, 200};

/*Amounts entered must be in pence.*/
int combinations(int amount, int size) {
    int comboCount = 0;

    if(amount > 0) {
        if(size >= 0 && amount >= coin[size])
            comboCount += combinations(amount - coin[size], size);
        if(size > 0) //don't do if size is 0
            comboCount += combinations(amount, size-1);
    } else if(amount == 0)
        comboCount++;

    return comboCount;
}

int combos(int amount) {
    int i = 0;
    //get largest coin that fits
    for(i = 7; coin[i] > amount && i >= 0; i--); 
    return combinations(amount, i);
}

int main() {
    cout << "Answer: " << combos(10) << endl;
    return 0;
}

possible duplicate of [Different ways of suming specific numbers to gain 100](http://stackoverflow.com/questions/6397827/different-ways-of-suming-specific-numbers-to-gain-100) — Ben Voigt, Jul 19 '11 at 22:10

score 2 · Accepted Answer · answered Jul 19 '11 at 22:35

2

Well, your code might return 11 because that's the right answer?

http://ideone.com/uxv4J

answered Jul 19 '11 at 22:35

Ben Voigt

277,958
43
419
720

Yep. That is what I get by hand and by program. – David Hammen Jul 19 '11 at 22:37
Whoops... yeah, apparently there are only 11 possibilities for 10. – paperbd Jul 19 '11 at 22:39

ruslik · Answer 2 · 2011-07-19T22:32:00.483

0

(comment, actually): Sorry, but I see only 10 combinations for 10 pences out of 1, 2 and 5:

10p:    0..5*2p + rest*1p     : 6 combinations
1x5p + 5p, that is
        0..2*2p + rest*1p     : 3 combinations
        1*5p                  : 1 combination

edited Jul 19 '11 at 22:32

answered Jul 19 '11 at 22:25

ruslik

14,714
1
39
40

1x10p coin counts, as well as 5x2p coins. – paperbd Jul 19 '11 at 22:37
You can also use a single 10p coin, so 11 ways total. – Ben Voigt Jul 19 '11 at 22:38
right, if there is also 10p coin, then add one more combination. (the last combination is actually 2x5p) – ruslik Jul 19 '11 at 22:40

Project Euler #31

2 Answers2