看动画轻松理解「递归」与「动态规划」 (4)

只挖第一座金矿

在只挖第一座金矿前面两个工人挖矿收益为 零，当有三个工人时，才开始产生收益为 200，而后即使增加再多的工人收益不变，因为只有一座金矿可挖。

2.挖第一座与第二座金矿

挖第一座与第二座金矿

在第一座与第二座金矿这种情况中，前面两个工人挖矿收益为 零，因为 W < 3,所以F(N,W) = F(N-1,W) = 0。

当有 三 个工人时，将其安排挖第 一 个金矿，开始产生收益为 200。

当有 四 个工人时，挖矿位置变化，将其安排挖第 二 个金矿，开始产生收益为 300。

当有 五、六 个工人时，由于多于 四 个工人的人数不足以去开挖第 一 座矿，因此收益还是为 300。

当有 七 个工人时，可以同时开采第 一 个和第 二 个金矿，开始产生收益为 500。

3.挖前三座金矿

这是「国王和金矿」 问题中最重要的一个动画之一，可以多看几遍

挖前三座金矿

4.挖前四座金矿

这是「国王和金矿」 问题中最重要的一个动画之一，可以多看几遍

挖前四座金矿

国王和金矿问题中的【规律】

仔细观察上面的几组动画可以发现：

对比「挖第一座与第二座金矿」和「挖前三座金矿」，在「挖前三座金矿」中，3 金矿 7 工人的挖矿收益，来自于 2 金矿 7 工人和 2 金矿 4 工人的结果，Max(500,300 + 350) = 650；

对比「挖前三座金矿」和「挖前四座金矿」，在「挖前四座金矿」中，4 金矿 10 工人的挖矿收益，来自于 3 金矿 10 工人和 3 金矿 5 工人的结果，Max(850,400 + 300) = 850；

国王和金矿问题中的【动态规划代码】 1代码来源：https://www.cnblogs.com/SDJL/archive/2008/08/22/1274312.html
2
3//maxGold[i][j] 保存了i个人挖前j个金矿能够得到的最大金子数，等于 -1 时表示未知
4int maxGold[max_people][max_n];
5
6int GetMaxGold(int people, int mineNum){
7    int retMaxGold;                            //声明返回的最大金矿数量
8    //如果这个问题曾经计算过
9    if(maxGold[people][mineNum] != -1){
10        retMaxGold = maxGold[people][mineNum]; //获得保存起来的值
11    }else if(mineNum == 0) {                   //如果仅有一个金矿时 [ 对应动态规划中的"边界"]
12        if(people >= peopleNeed[mineNum])      //当给出的人数足够开采这座金矿
13            retMaxGold = gold[mineNum];        //得到的最大值就是这座金矿的金子数
14        else                                   //否则这唯一的一座金矿也不能开采
15            retMaxGold = 0;                    //得到的最大值为 0 个金子
16    }else if(people >= peopleNeed[mineNum])    // 如果人够开采这座金矿[对应动态规划中的"最优子结构"]
17    {
18        //考虑开采与不开采两种情况，取最大值
19        retMaxGold = max(
20                         GetMaxGold(people - peopleNeed[mineNum],mineNum - 1) + gold[mineNum],
21                         GetMaxGold(people,mineNum - 1)
22                         );
23    }else//否则给出的人不够开采这座金矿 [ 对应动态规划中的"最优子结构"]
24    {
25        retMaxGold = GetMaxGold(people,mineNum - 1);     //仅考虑不开采的情况
26        maxGold[people][mineNum] = retMaxGold;
27    }
28    return retMaxGold;
29}