プロジェクトオイラー＃31

Question

問題の説明：

イギリスの通貨はポンドで構成され、£、およびペンス、P、および 8枚のコインが全身循環にありますされています

1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p). 

1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p 

どのように多くの異なる方法で£2を作ることができますか？

私は自分自身のアルゴリズムを考え出して失敗しました。だから、私はthis one（受け入れられた答え）に来た。私はここでC + +でそれを複製しようとしました。私が1,2,5をmain（）関数のcombos（）に入力すると、正しい答えが返されますが、10の場合は11が返されます。アルゴリズムの問​​題は何ですか？

#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; 
} 

Answer 1

ことだからまあ、あなたのコードは11を返すことがあります正解？

• http://ideone.com/uxv4J

Answer 2

は（実際にはコメント、）：申し訳ありませんが、私は1、2及び5のうち、10 pencesのための唯一の10の組み合わせを参照してください。

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