有1分,2分,5分,10分四种硬币，每种硬币数量无限，给定n

[问答题]

有1分,2分,5分,10分四种硬币，每种硬币数量无限，给定n分钱，求有多少种组合可以组合成n分钱?

推荐

爱卖萌的小瑞

①，四层循环
②，使用回溯法在空间中搜索
代码为思路：定义控制台应用程序的入口点。

#include "stdafx.h"

using namespace std;
int count = 0;
int Target = 0;
int coin[4] = {1, 2, 5, 10};
int total = 0;
vector solution;
void dfs(int index)
{
    if ( total == Target )
    {
        count++;
        cout << count << ":" ;
        for ( int i = 0; i < (int)solution.size(); i++)
        {
            cout << solution[i] << " ";
        }
        cout << endl;
        return;
    }
    if ( total > Target )
        return;
    for ( int i = index; i < 4; i++)
    {
        total += coin[i];
        solution.push_back( coin[i] );
        dfs(i);
        solution.pop_back();
        total -= coin[i];
    }
}
int _tmain(int argc, _TCHAR *argv[])
{
    while (1)
    {
        count = 0;
        cin >> Target;
        dfs(0);
        cout << count << endl;
    }
    return 0;
}

编辑于 2015-02-06 14:39:41 回复(0)