金矿问题

10.金矿问题

题目

有5座金矿，每座金矿的黄金储量不同，需要参与挖掘的工人人数也不同。例如有的金矿储量是500kg黄金，需要5个工人来挖掘，有的金矿储量是200kg黄金，需要3个工人来挖掘......

如果参与挖矿的工人的总数是10。每座金矿要么全挖，要么不挖，不能派出一半人挖取一半的金矿。要求计算出，最大挖取的黄金值。

```java
int[] g = {400, 500, 200, 300, 350};//金矿储量
int[] p = {5, 5, 3, 4, 3};//挖取需要的工人数量
```

思路

如果使用贪心算法，局部情况最优解，但是整体上却未必最优。比如，计算每个金矿的人均产值，为{80,100,66.6,75,116.6}，单位是kg/人，每一步最优的话，就是挖取350/3人的金矿，和500/5人的金矿，然后就无法挖取了，这里挖取的金矿是850kg，但是还有比这个高的，400/5，500/5人的挖取就是900kg。

这里提供正确思路，其实这个问题，是典型的动态规划题目。动态规划就是把复杂的问题简化为规模较小的子问题，再从简单的子问题自底向上的一步一步递推，最终得到复杂问题的最优解。

对于金矿，只有挖和不挖，两种选择。假设350kg/3人的，金矿不挖，问题就会转成10人挖前4个金矿的最优解，但是这个只是假设的最优，是否最优，还需要和挖350kg/3人的金矿，然后加上7个人挖前4个的金矿的最优解。比较那个大，那个就是最优解。这两种情况，就是全局问题的最优子结构。

就这样，对于每个金矿，都有挖和不挖，问题就一分为二，二分为四，一直把问题简化到0个金矿或0个工人时的最优选择，这个收益结果显然是0，也就是问题的边界。

这些就是动态规划的要点，确定问题的，全局最优解，和最优子结构之间的关系，以及问题的边界。这个关系用数学公式表达的话，就是状态转移方程式。

金矿数量为n，工人数量为w，金矿的含金量设为数组g[]，金矿所需开采人数为p[]。设f(n,w)为n个金矿，w个工人时的最优收益函数，则该问题的状态转移方程式为，特别重要，后续2，3版本的代码，都要理解这个状态转移函数。

```txt
f(n,w) = 0(n=0 或 w=0) //问题的边界
f(n,w) = f(n-1,w) (n>=1,w=1,w>=p[n-1]) //工人数量，可以挖取当前金矿
```

代码

```java
//递归
    /**
     * 获取金矿最佳收益
     *
     * @param n 当前金矿数量
     * @param w 当前工人人数
     * @param g 金矿含量数组
     * @param p 对应金矿含量所需人数数组
     * @return 返回当前工人人数，和金矿数量的最佳收益函数
     * 递归方式计算，的时间复杂度为O(2^n)，适合于金矿数量小时的情况
     * 注意这个n是当前金矿的数量，就好比每一个金矿都要分成2种情况，每个金矿下的其他金矿又有两种情况，组合起来看是一个满二叉树，
     * 节点的个数和层级有关也就是金矿的数量有关为2^n(n为层级，这个问题中为金矿的个数)
     */
    public static int getBestGoldMining(int n, int w, int[] g, int[] p) {
        if (n <= 0 || w <= 0)
            return 0;
        if (w < p[n - 1])
            return getBestGoldMining(n - 1, w, g, p);
        return Math.max(getBestGoldMining(n - 1, w, g, p), getBestGoldMining(n - 1, w - p[n - 1], g, p) + g[n - 1]);
    }
```

注意，上述代码是正确的，但是时间复杂度，却来到了2^n。低效的原因，是进行了很多重复运算。

可以，使用一个表格，二维数组，来存储这些中间值。表格最左侧代表不同的金矿选择范围，从上到下，每多增加1行，就代表多1个金矿可供选择，也就是f(n,w)函数中的n值。此时，最后1行最后1个格子的值，就是最终要求的结果，即5个金矿、10个工人的最优收益。

| 1个工人 | 2个工人 | 3个工人 | 4个工人 | 5个工人 | 6个工人 | 7个工人 | 8个工人 | 9个工人 | 10个工人
---|---|---|---|---|---|---|---|---|---|---
400kg/5人 | | | | | | | | | |
500kg5人 | | | | | | | | | |
200kg/3人 | | | | | f(3,5) | | | | |
300kg/4人 | | | | | | | | | |
350kg/3人 | | | | | | | | | | f(5,10)

```java
/**
     * @param n 金矿数量 这个值，是等于g.length的，可以省略
     * @param w 当前工人数量
     * @param g 每个金矿存储数量数组
     * @param p 每个金矿开采所需工人数量数组
     * @return 时间复杂杜和空间复杂度都为O(nw) 在w值较小的情况下，该算法比递归的性能好，如果w很大的，而n很小的情况下，
     * 就是2^n < nw的情况下，递归会比该算法好。
     * 算法是对不同情况下问题解决的一种方式，没有任何情况下都最优的解法，只有适合当前情况的不错的选择。
     */
    public static int getBestGoldMiningV2(int n, int w, int[] g, int[] p) {
        //抽象一个二维数组，用于暂存最优收益函数的临时结果
        int[][] result = new int[n + 1][w + 1];
        /*
        * 为什么是n+1和w+1，因为要利用int[][]数组的默认值为0这个特性，以及在当前问题下，n=0,和w=0时，f(n,w) = 0
        * int[0][x](0=

```java
/**
     * @param n 金矿数量 这个值，是等于g.length的，可以省略
     * @param w 当前工人数量
     * @param g 每个金矿存储数量数组
     * @param p 每个金矿开采所需工人数量数组
     * @return 时间复杂度O(nw)，空间复杂杜为0(n)
     */
    public static int getBestGoldMiningV3(int n, int w, int[] g, int[] p){
        int[] results = new int[w+1];//暂存一行的临时数据
        //填充一位数组
        for(int i = 1;i <= g.length; i++){
            //注意，此处对于f(n,w)值的计算，是从w -> 1，也就是从右往左遍历，
            //原因是，需要使用数组的旧值，作为上一行(针对第二版代码来说)的值，因为新值(是下一行的)需要用旧值(是上一行的)进行计算，
            //如果，从左往右计算，则在计算一行后面的新值时，使用的也是新的数据，就会导致计算的结果不正确
            for(int j = w; j >= 1; j--){
                if(j >= p[i-1]){
                    results[j] = Math.max(results[j], results[j-p[i-1]] + g[i-1]);
                }
            }
        }
        return results[w];
    }
```