Problem31 2ポンドを作る組み合わせの数

問題

イギリスでは硬貨はポンドとペンスがあり，一般的に流通している硬貨は以下の8種類である.
1ペンス, 2ペンス, 5ペンス, 10ペンス, 20ペンス, 50ペンス, 1ポンド(100ペンス) , 2ポンド(200ペンス)

以下の方法で2ポンドを作ることが可能である．
1×1ポンド + 1×50ペンス + 2×20ペンス + 1×5ペンス + 1×2ペンス + 3×1ペンス

これらの硬貨を使って2ポンドを作る方法は何通りあるか?

ソース

#include <valarray>
#include <stack>
#include <string>
#include <Windows.h>
#include <iostream>

struct DefineKeiro{
    int X;
    std::valarray<int> MaisuuArr;
    int SumVal;
};

void main()
{
    int MoneyArr[] = {1, 2, 5, 10, 20, 50, 100, 200};
    const int MoneyArrUB = sizeof(MoneyArr)/sizeof(int)-1;

    std::stack<DefineKeiro> stk;
    for(int I=0;I<=MoneyArrUB;I++){
        DefineKeiro WillPush;
        WillPush.X = I;
        WillPush.MaisuuArr = std::valarray<int>(0,MoneyArrUB+1);
        WillPush.MaisuuArr[I] = 1;
        WillPush.SumVal= MoneyArr[I];
        stk.push(WillPush);
    }

    int AnswerCnt = 0;
    while (stk.empty() == false){
        DefineKeiro Popped = stk.top(); stk.pop();
        if (Popped.SumVal == 200) {
            std::string WillOut;
            char WKArr[100]; wsprintf(WKArr,"%d番目", ++AnswerCnt);
            WillOut += WKArr;

            for(int I=0;I<=(int)Popped.MaisuuArr.size()-1;I++){
                if(Popped.MaisuuArr[I] == 0) continue;
                wsprintf(WKArr,",%dポンドが%d",MoneyArr[I],Popped.MaisuuArr[I]);
                WillOut += WKArr;
            }
            std::cout << WillOut << std::endl;
            continue;
        }

        for (int I=Popped.X;I<=MoneyArrUB;I++) {
            DefineKeiro WillPush;
            WillPush.SumVal = Popped.SumVal + MoneyArr[I];
            if (WillPush.SumVal > 200) break;
            WillPush.X = I;
            WillPush.MaisuuArr = Popped.MaisuuArr;
            WillPush.MaisuuArr[I]++;
            stk.push(WillPush);
        }
    }
}

実行結果

省略
73675番目,1ポンドが191,2ポンドが2,5ポンドが1
73676番目,1ポンドが192,2ポンドが4
73677番目,1ポンドが193,2ポンドが1,5ポンドが1
73678番目,1ポンドが194,2ポンドが3
73679番目,1ポンドが195,5ポンドが1
73680番目,1ポンドが196,2ポンドが2
73681番目,1ポンドが198,2ポンドが1
73682番目,1ポンドが200

解説

深さ優先探索で組み合わせを列挙してます。