动态规划算法

前言
最近帮同学写一个程序，给出100多个金额，用数组表示为money[1-100]，再给出一个数额SUM。如果money数组里面有哪几项之和等于SUM，那么这几项就是符合条件的一个组合。现在需要做的是，找出所有符合要求的组合。

举一个简单的例子，假设money为{1,1,2,3,4}，和为6的所有组合为1+1+4, 1+2+3，1+2+3，2+4。

对于我同学给的这个程序要求，不算不知道，一算吓一跳，100个数的所有组合情况是2的100次方，是天文数字了。（本机测试2的32次方次数的浮点运算消耗30秒左右时间）

所以没有办法罗列出所有的组合，而且在易做图上查找NPC问题(Non-deterministic Polynomial complete problem非确定多项式完备问题）时，第一个例子就是这种子集合加总问题（说白一点就是组合之和）。易做图上提到：“这个问题的答案非常容易验证，但目前没有任何一个够快的方法可以在合理的时间内（意即多项式时间）找到答案。只能一个个将它的子集取出来一一测试，它的时间复杂度是Ο（2n），n是此集合的元素数量。”

当然，不能因为罗列所有的组合是不可行的，就不写这个程序了吧，代码是死的，人是活的。可以制定策略嘛，比如说如果一个组合里面最多只能有5项；尝试遍历组合的时候，只要找到了10种或者20种组合，后面的就不再计算了。而对于实在搜索不到的组合，我们可以采用超时的方式，比如计算30秒或1分钟之后就不再计算了，而是返回没有找到可行的组合。

说了这么多，好像和我写的标题还没有什么联系，其实是这样的，一开始我是采用回溯法去解决上面的问题的，但是我一直在想是不是可以用背包算法或者动态规划的算法来写这个程序（当然最后得到的结论是不可行）。

因为以前看过动态规划方面的一些资料，现在又忘的差不多了，所以想回头看一下，顺便学习一下。= =

这里有一篇很不错的讲动态规划的文章：http://hawstein.com/posts/dp-novice-to-advanced.html，里面通过实例由浅入深的讲解了动态规划的使用。下面我举一下里面的两个例子。

第一个例子需要的最少硬币数：
如果我们有面值为1元、4元和5元的硬币若干枚，如何用最少的硬币凑够12元（12可替换为任意的N>0）？

注意：在这里贪心算法获得的结果不是最优的，如果按照每次都优先选最大面值的，那么会先拿两次5元得到10元，剩下的两元再拿两个1元的，总共需要4枚硬币。而更优化的方案是拿3枚4元的硬币。

下面我们就来看看该如何解决这个问题。

根据已经有的硬币面值，我们知道最后一次可以选择的硬币有3种方案（1元，4元和5元），如果最后一次是选择1元硬币凑够12元的，那么倒数第二步就应该是凑够了12-1= 11元。同理，如果最后一次是选择4元凑够12元的，则倒数第二步就应该是凑够了12-4 = 8元，如果最后一次是选择5元而凑够12元的，则倒数第二步就应该是凑够了12-5 = 7元。

换句话说：只有3种状态能够通过只取一枚硬币就凑够12元，分别是11元、8元、7元。现在假设凑够11元、8元、7元所需要的最少硬币数量是x、y、z，那么凑够12元所需要的最少硬币数量就是x,y,z里面的最小值 + 1。用表达式表示就是min(x,y,z)+1，从递归的角度来看问题就被递归下降分解了，从原来的求凑够12元需要的最少硬币数转换成了求凑够11元、8元、7元所需要的最少硬币数。那么把这种递归下降分解的思路继续拓展下去，最终会终止到1元硬币的情况。

我们用N(i)表示凑够i元需要的最少硬币数量。那么N(12) = min ( N(11), N(8), N(7) ) + 1. 转换成更一般的公式就是N(i) = min ( N(i-1), N(i-4), N(i-5) ) + 1.根据这个公式我们可以写出递归函数，代码如下：

[cpp]
int GetMinCoinCount(int nSum)
{
    if (1 == nSum || 4 == nSum || 5 == nSum)
    {
        return 1;
    }
    if (nSum > 5)
    {
        return MIN_THREE(GetMinCoinCount(nSum-1), GetMinCoinCount(nSum-4), GetMinCoinCount(nSum-5))+1;
    }
    else if (nSum > 4)
    {
        return MIN_TWO(GetMinCoinCount(nSum-1), GetMinCoinCount(nSum-4))+1;
    }
    else
    {
        return GetMinCoinCount(nSum-1)+1;
    }
}

int GetMinCoinCount(int nSum)
{
    if (1 == nSum || 4 == nSum || 5 == nSum)
    {
        return 1;
    }
    if (nSum > 5)
    {
        return MIN_THREE(GetMinCoinCount(nSum-1), GetMinCoinCount(nSum-4), GetMinCoinCount(nSum-5))+1;
    }
    else if (nSum > 4)
    {
        return MIN_TWO(GetMinCoinCount(nSum-1), GetMinCoinCount(nSum-4))+1;
    }
    else
    {
        return GetMinCoinCount(nSum-1)+1;
    }
}递归虽然代码写起来很简单，理解起来也不困难，但是效率非常低，究其原因就是因为我们重复计算了太多中间值，比如用上面的代码计算凑够12元所需要的最少硬币数，上面的这个函数被调用了2620次之多（在函数内部加一个静态变量或全局变量，进行递增计算即可）。

当需要凑够27元时，GetMinCoinCount函数被调用次数已经达到29,1208,9123次（29亿）。消耗的时间在几十秒的数量级。下面是测试代码和测试结果。

[cpp]
for (int m = 12; m < 30; m++)
    {
        g_i = 0;
        int n = GetMinCoinCount(m);
        printf("计算凑成%d元最少需要的硬币数量,调用GetMinCoinCount函数0x%08X次。\r\n", m, g_i);
    }

计算凑成12元最少需要的硬币数量,调用GetMinCoinCount函数0x00000A3C次。
计算凑成13元最少需要的硬币数量,调用GetMinCoinCount函数0x0000184B次。
计算凑成14元最少需要的硬币数量,调用GetMinCoinCount函数0x00003535次。
计算凑成15元最少需要的硬币数量,调用GetMinCoinCount函数0x00003F7A次。
计算凑成16元最少需要的硬币数量,调用GetMinCoinCount函数0x00011692次。
计算凑成17元最少需要的硬币数量,调用GetMinCoinCount函数0x0004951B次。
计算凑成18元最少需要的硬币数量,调用GetMinCoinCount函数0x000A1756次。
计算凑成19元最少需要的硬币数量,调用GetMinCoinCount函数0x001561CA次。
计算凑成20元最少需要的硬币数量,调用GetMinCoinCount函数0x00180DE3次。
计算凑成21元最少需要的硬币数量,调用GetMinCoinCount函数0x006A7855次。
计算凑成22元最少需要的硬币数量,调用GetMinCoinCount函数0x01C2A51C次。
计算凑成23元最少需要的硬币数量,调用GetMinCoinCount函数0x03E4E8B7次。
计算凑成24元最少需要的硬币数量,调用GetMinCoinCount函数0x083F6AC5次。
计算凑成25元最少需要的硬币数量,调用GetMinCoinCount函数0x09447736次。
计算凑成26元最少需要的硬币数量,调用GetMinCoinCount函数0x29019F66次。
计算凑成27元最少需要的硬币数量,调用GetMinCoinCount函数0xAD92F423次。

for (int m = 12; m < 30; m++)
    {
        g_i = 0;
        int n = GetMinCoinCount(m);
        printf("计算凑成%d元最少需要的硬币数量,调用GetMinCoinCount函数0x%08X次。\r\n", m, g_i);
    }

计算凑成12元最少需要的硬币数量,调用GetMinCoinCount函数0x00000A3C次。
计算凑成13元最少需要的硬币数量,调用GetMinCoinCount函数0x0000184B次。
计算凑成14元最少需要的硬币数量,调用GetMinCoinCount函数0x00003535次。
计算凑成15元最少需要的硬币数量,调用GetMinCoinCount函数0x00003F7A次。
计算凑成16元最少需要的硬币数量,调用GetMinCoinCount函数0x00011692次。
计算凑成17元最少需要的硬币数量,调用GetMinCoinCount函数0x0004951B次。
计算凑成18元最少需要的硬币数量,调用GetMinCoinCount函数0x000A1756次。
计算凑成19元最少需要的硬币数量,

补充：软件开发 , C++ ,