找零钱算法

现在有大量的1元，2元，5元，10元，20元和50元面额的纸币，给定一个金额总数，用这些零钱找开，求一共多少种找法。比如4元有 :1111, 211, 22, 三种找法

有一种快的算法和一种慢的算法

这貌似跟走楼梯那个算法是差不多的，不过我不记得怎么算得了。。汗

应该可以用类似背包问题的DP方法，只不过由于数目不确定需要稍微有点变化

Dp 或者回溯 clrs里讲过

Dp 或者回溯 clrs里讲过
ForeverYoung 发表于 2011-6-7 03:36

    所跌死捏～～～

//Two Solution:
//one is direct search, exponential time complexity, sort like NPC

//Another is dynamic programming, typical pseudo DP for NPC problem, equation:
//F(x,y) = f(x, y-1) + f(x-v(y), y-1) + f(x-2v(y), y-1) + ... + f(x-s*v(y), y-1), ((s+1)*v(y) > x)
//x is the amount of money, v(y) is the value of the change coin, y is the index

int WaysOfChange1(int nMoney, int a[], int n)
{
        assert(nMoney >= 0 && n >= 0);
        assert(a);

        if (0 == nMoney) return 1;
        if (0 == n) return 0;

        int nRet = 0;
        int nCur = 0;
        while (nCur*a[0] <= nMoney)
        {
                nRet += WaysOfChange1(nMoney-nCur*a[0], a+1, n-1);
                nCur++;
        }

        return nRet;
}

int WaysOfChange2(int nMoney, int a[], int n)
{
        assert(nMoney > 0 && a && n > 0);

        sort(a, a+n);
        int** pDP = new int* [nMoney];
        for (int i = 0; i < nMoney; i++)
                pDP[i] = new int[n];

        //init
        for (int i = 0; i < nMoney; i++)
                pDP[i][0] = ((i+1)%a[0]) == 0 ? 1 : 0;
        for (int i = 0; i < n; i++)
                pDP[0][i] = (1%a[i]) == 0 ? 1 : 0;

        //F(x,y) = f(x, y-1) + f(x-v(y), y-1) + f(x-2v(y), y-1) + ... + f(x-s*v(y), y-1), ((s+1)*v(y) > x)
        for (int i = 1; i < nMoney; i++)
                for (int j = 1; j < n; j++)
                {
                        int nVal = 0;
                        int nCur = 0;
                        while (nCur*a[j] <= i+1)
                        {
                                if (nCur*a[j] == i+1)
                                        nVal += 1;
                                else
                                        nVal += pDP[i-nCur*a[j]][j-1];

                                nCur++;
                        }
                        pDP[i][j] = nVal;
                }

        int nRet = pDP[nMoney-1][n-1];
        for (int i = 0; i < nMoney; i++)
                delete []pDP[i];
        delete []pDP;

        return nRet;
}