5.11.1 一个关于财富自由的问题
下面考你一道算法题，这个算法题目和钱有关系。
题目
很久很久以前，有一位国王拥有5座金矿，每座金矿的黄金储量不同，需要参与挖掘的工人人数也不同。例如有的金矿储量是500kg黄金，需要5个工人来挖掘；有的金矿储量是200kg黄金，需要3个工人来挖掘……
如果参与挖矿的工人的总数是10。每座金矿要么全挖，要么不挖，不能派出一半人挖取一半的金矿。要求用程序求出，要想得到尽可能多的黄金，应该选择挖取哪几座金矿？
哇，要是我家也有5座金矿，我就财富自由了，也用不着来你这里面试了！
说正经的！关于这道题你有什么思路吗？
题目好复杂啊，让我想想……
我想到了一个办法！我们可以按照金矿的性价比从高到低进行排序，优先选择性价比最高的金矿来挖掘，然后是性价比第2的……
按照小灰的思路，金矿按照性价比从高到低进行排序，排名结果如下。
第1名，350kg黄金/3人的金矿，人均产值约为116.6kg黄金。
第2名，500kg黄金/5人的金矿，人均产值为100kg黄金。
第3名，400kg黄金/5人的金矿，人均产值为80kg黄金。
第4名，300kg黄金/4人的金矿，人均产值为75kg黄金。
第5名，200kg黄金/3人的金矿，人均产值约为66.6kg黄金。
由于工人数量是10人，小灰优先挖掘性价比排名为第1名和第2名的金矿之后，工人还剩下2人，不够再挖掘其他金矿了。
所以，小灰得出的最佳金矿收益是350+500即850kg黄金。
怎么样？我这个方案妥妥的吧？
你的解决思路是使用贪心算法。这种思路在局部情况下是最优解，但是在整体上却未必是最优的。
给你举个例子吧，如果我放弃性价比最高的350kg黄金/3人的金矿，选择500kg黄金/5人和400kg黄金/5人的金矿，加起来收益是900kg黄金，是不是大于你得到的850kg黄金？
啊，还真是呢！
呵呵，没关系，回家等通知去吧！
5.11.2 解题思路
小灰，你刚刚去面试了？结果怎么样？
唉……
大黄，你能不能给我讲讲，怎么来求解金矿问题呀？
好啊，这是一个典型的动态规划 题目，和著名的“背包问题”类似。
动态规划？好“高大上”的概念呀！
其实也没有那么高深啦。所谓动态规划，就是把复杂的问题简化成规模较小的子问题，再从简单的子问题自底向上一步一步递推，最终得到复杂问题的最优解。
哦，说了半天还是没听明白……
没关系，让我们具体分析一下这个金矿问题，你就能明白动态规划的核心思想了。
首先，对于问题中的金矿来说，每一个金矿都存在着“挖”和“不挖”两种选择。
让我们假设一下，如果最后一个金矿注定不被挖掘，那么问题会转化成什么样子呢？
显然，问题简化成了10个工人在前4个金矿中做出最优选择。
相应地，假设最后一个金矿一定会被挖掘，那么问题又转化成什么样子呢？
由于最后一个金矿消耗了3个工人，问题简化成了7个工人在前4个金矿中做出最优选择。
这两种简化情况，被称为全局问题的两个最优子结构 。
究竟哪一种最优子结构可以通向全局最优解呢？换句话说，最后一个金矿到底该不该挖呢？
那就要看10个工人在前4个金矿的收益，和7个工人在前4个金矿的收益+最后一个金矿的收益 谁大谁小了。
同样的道理，对于前4个金矿的选择，我们还可以做进一步简化。
首先针对10个工人4个金矿这个子结构，第4个金矿（300kg黄金/4人）可以选择挖与不挖。根据第4个金矿的选择，问题又简化成了两种更小的子结构。
1. 10个工人在前3个金矿中做出最优选择。
2. 6（10-4=6）个工人在前3个金矿中做出最优选择。
相应地，对于7个工人4个金矿这个子结构，第4个金矿同样可以选择挖与不挖。根据第4个金矿的选择，问题也简化成了两种更小的子结构。
1. 7个工人在前3个金矿中做出最优选择。
2. 3（7-4=3）个工人在前3个金矿中做出最优选择。
……
就这样，问题一分为二，二分为四，一直把问题简化成在0个金矿或0个工人时的最优选择，这个收益结果显然是0，也就是问题的边界 。
这就是动态规划的要点：确定全局最优解和最优子结构之间的关系，以及问题的边界。这个关系用数学公式来表达的话，就叫作状态转移方程式 。
好像有点明白了……那这个所谓的状态转移方程式是什么样子？
我们把金矿数量设为n，工人数量设为w，金矿的含金量设为数组g[]，金矿所需开采人数设为数组p[]，设F（n，w）为n个金矿、w个工人时的最优收益函数，那么状态转移方程式如下。
F(n,w) = 0 (n=0或w=0)
问题边界，金矿数为0或工人数为0的情况。
F(n,w) = F(n-1,w) (n≥1, w
当所剩工人不够挖掘当前金矿时，只有一种最优子结构。
F(n,w) = max(F(n-1,w), F(n-1,w-p[n-1])+g[n-1]) (n≥1, w≥p[n-1])
在常规情况下，具有两种最优子结构（挖当前金矿或不挖当前金矿）。
小灰，既然有了状态转移方程式，你能实现代码来求出最优收益吗？
这还不简单？用递归就可以解决！
1. /**
2. * 获得金矿最优收益
3. * @param w 工人数量
4. * @param n 可选金矿数量
5. * @param p 金矿开采所需的工人数量
6. * @param g 金矿储量
7. */
8. public static int getBestGoldMining(int w, int n,
int[] p, int[] g){
9. if(w==0 || n==0){
10. return 0;
11. }
12. if(w
13. return getBestGoldMining(w, n-1, p, g);
14. }
15. return Math.max(getBestGoldMining(w, n-1, p, g),
getBestGoldMining(w-p[n-1], n-1, p, g)+g[n-1]);
16. }
17.
18. public static void main(String[] args) {
19. int w = 10;
20. int[] p = {5, 5, 3, 4 ,3};
21. int[] g = {400, 500, 200, 300 ,350};
22. System.out.println(" 最优收益：" + getBestGoldMining(w,
g.length, p, g));
23. }
OK，这样确实可以得到正确结果，不过你思考过这段代码的时间复杂度吗？
让我分析一下啊……全局问题经过简化，会拆解成两个子结构；两个子结构再次简化，会拆解成4个更小的子结构……就像下图一样。
我的天哪，这样算下来，如果金矿数量是n，工人数量充足，时间复杂度就是O(2 n ) ！
没错，现在我们的题目中只有5个金矿，问题还不算严重。如果金矿数量有50个，甚至100个，这样的时间复杂度是根本无法接受的。
啊，那该怎么办呢？
首先来分析一下递归之所以低效的根本原因，那就是递归做了许多重复的计算，看看下面的图你就明白了。
在上图中，标为红色的方法调用是重复的。可以看到F（2,7）、F（1,7）、F（1,2），这几个入参相同的方法都被调用了两次。
当金矿数量为5时，重复调用的问题还不太明显，当金矿数量越多，递归层次越深，重复调用也就越来越多，这些无谓的调用必然会降低程序的性能。
那我们怎样避免这些重复调用呢？
这就要说到动态规划的另一个核心要点：自底向上求解 。让我们来详细演示一下这种求解过程。
在进行求解之前，先准备一张表格，用于记录选择金矿的中间数据。
表格最左侧代表不同的金矿选择范围，从上到下，每多增加1行，就代表多1个金矿可供选择，也就是F（n，w）函数中的n值。
表格的最上方代表工人数量，从1个工人到10个工人，也就是F（n，w）函数中的w值。
其余空白的格子，都是等待填写的，代表当给出n个金矿、w个工人时的最优收益，也就是F（n，w）的值。
举个例子，下图中绿色的这个格子里，应该填充的是在有5个工人的情况下，在前3个金矿可供选择时，最优的黄金收益。
下面让我们从第1行第1列开始，尝试把空白的格子一一填满，填充的依据就是状态转移方程式。
对于第1行的前4个格子，由于w
F(n,w) = F(n-1,w) (n>1, w
带入求解：
F(1,1) = F(1-1,1) = F(0,1) = 0
F(1,2) = F(1-1,2) = F(0,2) = 0
F(1,3) = F(1-1,3) = F(0,3) = 0
F(1,4) = F(1-1,4) = F(0,4) = 0
第1行的后6个格子怎么计算呢？此时w≥p[n-1]，对于如下公式：
F(n,w) = max(F(n-1,w), F(n-1,w-p[n-1])+g[n-1]) (n>1, w≥p[n-1]);
带入求解：
F(1,5) = max(F(1-1,5), F(1-1,5-5)+400) = max(F(0,5), F(0,0)+400) = max(0, 400) = 400
F(1,6) = max(F(1-1,6), F(1-1,6-5)+400) = max(F(0,6), F(0,1)+400) = max(0, 400) = 400
……
F(1,10) = max(F(1-1,10), F(1-1,10-5)+400) = max(F(0,10), F(0,5)+400) = max(0, 400) = 400
对于第2行的前4个格子，和第1行同理，由于w
F(n,w) = F(n-1,w) (n>1, w
带入求解：
F(2,1) = F(2-1,1) = F(1,1) = 0
F(2,2) = F(2-1,2) = F(1,2) = 0
F(2,3) = F(2-1,3) = F(1,3) = 0
F(2,4) = F(2-1,4) = F(1,4) = 0
第2行的后6个格子，和第1行同理，此时w≥p[n-1]，对应的状态转移方程式如下：
F(n,w) = max(F(n-1,w), F(n-1,w-p[n-1])+g[n-1]) (n>1, w≥p[n-1])
带入求解：
F(2,5) = max(F(2-1,5), F(2-1,5-5)+500) = max(F(1,5), F(1,0)+500) = max(400, 500) = 500
F(2,6) = max(F(2-1,6), F(2-1,6-5)+500) = max(F(1,6), F(1,1)+500) = max(400, 500) = 500
……
F(2,10) = max(F(2-1,10), F(2-1,10-5)+500) = max(F(1,10), F(1,5)+500) = max(400, 400+500) = 900
第3行的计算方法如出一辙。
再接再厉，计算出第4行的答案。
最后，计算出第5行的结果。
此时，最后1行最后1个格子所填的900就是最终要求的结果，即5个金矿、10个工人的最优收益是900kg黄金。
好了，这就是动态规划自底向上的求解过程。
哇，这个方式还真有意思！那么，怎么用代码来实现呢？
在程序中，可以用二维数组来代表所填写的表格，让我们看一看代码吧。
1. /**
2. * 获得金矿最优收益
3. * @param w 工人数量
4. * @param p 金矿开采所需的工人数量
5. * @param g 金矿储量
6. */
7. public static int getBestGoldMiningV2(int w, int[] p, int[] g){
8. //创建表格
9. int[][] resultTable = new int[g.length+1][w+1];
10. //填充表格
11. for(int i=1; i<=g.length; i++){
12. for(int j=1; j<=w; j++){
13. if(j
14. resultTable[i][j] = resultTable[i-1][j];
15. }else{
16. resultTable[i][j] = Math.max(resultTable[i-1]
[j], resultTable[i-1][j-p[i-1]]+ g[i-1]);
17. }
18. }
19. }
20. //返回最后1个格子的值
21. return resultTable[g.length][w];
22. }
小灰，你说说上述代码的时间复杂度和空间复杂度分别是怎样的？
程序利用双循环来填充一个二维数组，所以时间复杂度和空间复杂度都是O(nw) ，比递归的性能好多啦！
是的，这段代码在时间上已经没有什么可优化的了，但是在空间上还可以做一些优化。
想一想，在表格中除第1行之外，每一行的结果都是由上一行数据 推导出来的。我们以4个金矿9个工人为例。
4个金矿、9个工人的最优结果，是由它的两个最优子结构，也就是3个金矿、5个工人和3个金矿、9个工人的结果推导而来的。这两个最优子结构都位于它的上一行。
所以，在程序中并不需要保存整个表格，无论金矿有多少座，我们只保存1行的数据即可。在计算下一行时，要从右向左统计（读者可以想想为什么从右向左），把旧的数据一个一个替换掉。
优化后的代码如下：
1. /**
2. * 获得金矿最优收益
3. * @param w 工人数量
4. * @param p 金矿开采所需的工人数量
5. * @param g 金矿储量
6. */
7. public static int getBestGoldMiningV3(int w, int[] p, int[] g){
8. //创建当前结果
9. int[] results = new int[w+1];
10. //填充一维数组
11. for(int i=1; i<=g.length; i++){
12. for(int j=w; j>=1; j--){
13. if(j>=p[i-1]){
14. results[j] = Math.max(results[j],
results[j-p[i-1]]+ g[i-1]);
15. }
16. }
17. }
18. //返回最后1个格子的值
19. return results[w];
20. }
哇，优化后的代码真的好简洁呀！
是呀，而且空间复杂度降低到了O(n) 。好了，关于金矿问题我们就讲解到这里，咱们下一节再会！