在只挖第一座金矿前面两个工人挖矿收益为 零,当有三个工人时,才开始产生收益为 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.html2
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}