看动画轻松理解「递归」与「动态规划」(完整版) (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}

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/wpjpww.html