很久很久以前，有一位国王拥有 5 座金矿，每座金矿的黄金储量不同，需要参与挖掘的工人人数也不同。例如有的金矿储量是 500kg 黄金，需要 5 个工人来挖掘；有的金矿储量是 200kg 黄金，需要 3 个工人来挖掘……

如果参与挖矿的工人的总数是 10。每座金矿要么全挖，要么不挖，不能派出一半人挖取一半的金矿。要求用程序求出，要想得到尽可能多的黄金，应该选择挖取哪几座金矿？

image.png
image.png
按照小灰的思路，金矿按照性价比从高到低进行排序，排名结果如下。

第 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 黄金。

image.png

解题思路

image.png
首先，对于问题中的金矿来说，每一个金矿都存在着「挖」和「不挖」两种选择。

让我们假设一下，如果最后一个金矿注定不被挖掘，那么问题会转化成什么样子呢？

显然，问题简化成了 10 个工人在前 4 个金矿中做出最优选择。

image.png

相应地，假设最后一个金矿一定会被挖掘，那么问题又转化成什么样子呢？

由于最后一个金矿消耗了 3 个工人，问题简化成了 7 个工人在前 4 个金矿中做出最优选择。
image.png
这两种简化情况，被称为全局问题的两个 最优子结构。
究竟哪一种最优子结构可以通向全局最优解呢？换句话说，最后一个金矿到底该不该挖呢？

那就要看 10 个工人在前 4 个金矿的收益，和 7 个工人在前 4 个金矿的收益 + 最后一个金矿的收益 谁大谁小了。

image.png
同样的道理，对于前 4 个金矿的选择，我们还可以做进一步简化。

首先针对 10 个工人 4 个金矿这个子结构，第 4 个金矿 300kg 黄金 / 4 人可以选择挖与不挖。根据第4个金矿的选择，问题又简化成了两种更小的子结构。

10 个工人在前 3 个金矿中做出最优选择。

6(10−4=6) 个工人在前 3 个金矿中做出最优选择。

相应地，对于 7 个工人 4 个金矿这个子结构，第 4 个金矿同样可以选择挖与不挖。根据第 4 个金矿的选择，问题也简化成了两种更小的子结构。

7 个工人在前 3 个金矿中做出最优选择。
3 (7−4=3) 个工人在前 3 个金矿中做出最优选择。
就这样，问题一分为二，二分为四，一直把问题简化成在 0 个金矿或 0 个工人时的最优选择，这个收益结果显然是 0，也就是问题的边界。

image.png

  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<p[n-1]){
  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. }
  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. }