Google code jam 2012 番外篇：巨款的人民币面值组合

据说是google 2011年秋季校园面试题目：

  如果你手上有100000000块钱，而人民币的面值有100，50，20，10，5，1，求这些钱共有>多少种组合可以得到你手上的钱。

我想到的方法是把所有情况遍历一遍，每次计数器加1：

#几种面值都可以被总价整出，所以问题变得简单，一种非elegant的代码。
amount = 100000000
nominal = [100, 50, 20, 10, 5, 1]
combination = set()

for a in range(amount//nominal[0] + 1):
    for b in range(amount//nominal[1] + 1):
        for c in range(amount//nominal[2] + 1):
            for d in range(amount//nominal[3] + 1):
                for e in range(amount//nominal[4] + 1):
                    remain = amount - (100*a + 50*b + 20*c + 10*d + 5*e)
                    if remain >= 0 and remain <= amount:
                        combination.add( (a,b,c,d,e,remain) )

print(len(combination))

for 循环可以优化，减少一定次数；顺次遍历所有情况，所以set()可以不要；python3效率不高，硬盘狂响，想必是内存不够了，换成C。

void calculate(int amount)
{
    int nominal[] = {100, 50, 20, 10, 5, 1};
    unsigned long long combination = 0;
    int a, b, c, d, e;
    int remain[4] = {0};

    for (a = 0; a <= amount / nominal[0]; ++a) {
        remain[0] = amount - 100 * a;
        for (b = 0; b <= remain[0] / nominal[1]; ++b) {
            remain[1] = remain[0] - 50 * b;
            for (c = 0; c <= remain[1] / nominal[2]; ++c) {
                remain[2] = remain[1] - 20 * c;
                for (d = 0; d <= remain[2] / nominal[3]; ++d) {
                    remain[3] = remain[2] - 10 * d;
                    for (e = 0; e <= remain[3] / nominal[4]; ++e) {
                        //printf("a:%d, b:%d, c:%d, d:%d, e:%d, f:%d\n",
                        //        a, b, c, d, e, remain[3]-5*e);
                        combination++;
                    }
                }
            }
        }
    }

    printf("\nCombination: %llu\n", combination);
    return ;
}

把for循环中每次计算的数字先计算了，降低计算量：

unsigned long long calculate2(int amount)
{
    int nominal[] = {100, 50, 20, 10, 5, 1};
    unsigned long long combination = 0;
    int a, b, c, d, e;
    int remain[4] = {0};
    int times[4] = {0};
    int n;

    n = amount / nominal[0] + 1;
    for (a = 0; a < n; ++a) {
        remain[0] = amount - 100 * a;
        times[0] = remain[0] / nominal[1] + 1;
        for (b = 0; b < times[0]; ++b) {
            remain[1] = remain[0] - 50 * b;
            times[1] = remain[1] / nominal[2] + 1;
            for (c = 0; c < times[1]; ++c) {
                remain[2] = remain[1] - 20 * c;
                times[2] = remain[2] / nominal[3] + 1;
                for (d = 0; d < times[2]; ++d) {
                    remain[3] = remain[2] - 10 * d;
                    times[3] = remain[3] / nominal[4] + 1;
                    for (e = 0; e < times[3]; ++e) {
                        //printf("a:%d, b:%d, c:%d, d:%d, e:%d, f:%d\n",
                        //        a, b, c, d, e, remain[3]-5*e);
                        combination++;
                    }
                }
            }
        }
    }

    printf("\nCombination: %llu\n", combination);
    return combination;
}

无论5元的出多少张，剩下的1元都可以来填补，所以最后一个循环可以略去：

void calculate3(int amount)
{
    int nominal[] = {100, 50, 20, 10, 5, 1};
    unsigned long long combination = 0;
    int a, b, c, d;
    int remain[4] = {0};
    int times[4] = {0};
    int n;

    n = amount / nominal[0] + 1;
    for (a = 0; a < n; ++a) {
        remain[0] = amount - 100 * a;
        times[0] = remain[0] / nominal[1] + 1;
        for (b = 0; b < times[0]; ++b) {
            remain[1] = remain[0] - 50 * b;
            times[1] = remain[1] / nominal[2] + 1;
            for (c = 0; c < times[1]; ++c) {
                remain[2] = remain[1] - 20 * c;
                times[2] = remain[2] / nominal[3] + 1;
                for (d = 0; d < times[2]; ++d) {
                    remain[3] = remain[2] - 10 * d;
                    times[3] = remain[3] / nominal[4] + 1;
                    combination += times[3];
                }
            }
        }
    }

    printf("\nCombination: %llu\n", combination);
    return ;
}

d变量的for循环还可以有一小步优化：

unsigned long long calculate5(int amount)
{
    int nominal[] = {100, 50, 20, 10, 5, 1};
    /* 估计这个64位的数不够容纳结果 */
    unsigned long long combination = 0;
    int a, b, c, d;
    int remain[4] = {0};
    int times[4] = {0};
    int n;

    n = amount / nominal[0] + 1;
    remain[0] = amount + 100; // +100 for the first time minus
    for (a = 0; a < n; ++a) {
        remain[0] -= 100;
        times[0] = remain[0] / nominal[1] + 1;
        remain[1] = remain[0] + 50;
        for (b = 0; b < times[0]; ++b) {
            remain[1] -= 50;
            times[1] = remain[1] / nominal[2] + 1;
            remain[2] = remain[1] + 20;
            for (c = 0; c < times[1]; ++c) {
                remain[2] -= 20;
                times[2] = remain[2] / nominal[3] + 1;
                for (d = 0; d < times[2]; ++d)
                    /* division 得到的是商，余数舍去，所以这个for不能用等差数列替换 */
                    combination += (remain[2] - 10*d) / nominal[4];
                combination += times[2];
            }
        }
    }

    printf("\nCombination: %llu\n", combination);
    return combination;
}

不能再优化了，我还写了一个check函数，检查变换的正确性：

int check()
{
    unsigned int i;
    int num[3] = {20, 107, 200};

    for (i = 0; i < sizeof(num) / sizeof(int); ++i)
    {
        unsigned long long cmp = calculate2(num[i]);
        unsigned long long ret = calculate5(num[i]);
        if (ret != cmp )
        {
            printf("Problem emerge: %llu, %llu at amount{%d}\n", ret, cmp, num[i]);
            return -1;
        }
    }
    return 0;
}

问题：

  目前，这个函数只可以计算小数据量，amount=10000时结果是  -->  174716753951，如果amount是10万，我的电脑跑12个小时都没出结果，并且可以知道unsigned long long 肯定是越界了好多次了，这时最好在加上计算越界多少次的功能，为了统计正确的结果。但实际上这么做已经没有意义了，因为需要考虑用一个更好的算法。

  实话实说，上面的代码都是垃圾，我也先入为主，暂时想不到更好的方法，有谁想到更好的方法了吗？