面试题之【挖金矿问题】

时间：03-27来源：作者：点击数：

1 题目

有一个国家发现了5座金矿，每座金矿的黄金储量不同，需要参与挖掘的工人数也不同。参与挖矿工人的总数是10人。每座金矿要么全挖，要么不挖，不能派出一半人挖取一半金矿。要求用程序求解出，要想得到尽可能多的黄金，应该选择挖取哪几座金矿？

2 思路

此问题是一道经典的动态规划（Dynamic programming）问题，简称DP问题，动态规划问题求解的三要素有一下三点：

全局最优解
最优子结构
问题的边界

对该金矿问题（假设共有n个金矿，共有w个工人，金矿的含金量数组为g，每个金矿所需开采工人的数组为p，假设F(n,w)为开采函数），可以进行如下分析，由题目可知，对一个金矿而言，该金矿要么都挖，要么都不挖，所以对任意一个金矿有以下两种情况：

不开采，则金矿数n减1，工人w数不变，则当前情况的最大开采量是F(n,w)=F(n-1,w)
开采，则金矿数n减1，由于有一部分工人开采了当前矿，那么所剩下的工人便是w-p[n-1]，由于已经开采了当前矿，所以当前情况下的最大开采量是max( F(n-1,w), g[n-1] + F(n-1, w-p[n-1]) )

那么该问题的边界值如下：

当w=0且w<p[0]，则F(1,w)=0
当w=0且w>p[0]，则F(1,w)=g[0]

3 代码实现

3.1 递归实现（自顶向下）

//递归实现
public int F(int n, int w, int[] g, int[] p) {
    if (w==0 || n==0)
        return 0;
    if (w < p[n-1]) //如果当前的工人数小于需要开采当前矿所需的人数，则不开采
        return F(n-1,w,g,p);
    return Math.max(F(n-1,w,g,p),g[n-1]+F(n-1,w-p[n-1],g,p));
}

由于递归实现是一种自顶向下的访问，类似一颗树，且该树中有很多节点被重复访问，所以此方法的算法复杂度较高，为O(2^n)。当金矿数量很多时，此方法的求解速度会很慢。

3.2 动态规划实现（自下向上）

动态规划的思路是一种类似贪心算法的思路（通过寻找局部最优解，一步一步找到全局最优解）。

DP求解思路：

画一张表，有n+1行，w+1列，从小到大计算每种情况的最大开采量，则有下表这张表：

一次计算，则有最后的计算结果，在有5个矿，10个工人的情况下，最大开采量是900。

Java代码实现：

//自底向上求解
public int greatestMiningGoldValue2(int n, int w, int[] g, int[] p) {
    int[][] miningArray = new int[n+1][w+1];
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= w; j++) {
            if (j < p[i-1])
                miningArray[i][j] = miningArray[i-1][j];
            else
                miningArray[i][j] = Math.max(miningArray[i-1][j],miningArray[i-1][j-p[i-1]]+g[i-1]);
        }
    }
    return miningArray[n][w];
}

算法复杂度分析：

该算法使用两个循环，一个外循环、一个内循环，外循环是矿的数量n，内循环是工人的个数w，所以时间复杂度是O(n*w)、由于使用一个数组，所以空间复杂度是O(n*w)。

3.3 在DP的基础上进一步优化空间

对于3.2中的算法，其实还可以进一步进行优化，从打印结果可以看出，其中有很多的数组空间是没有被完全利用，所以这一些空间还可以进一步缩减，以扩大空间的使用效率。

思路：可以每次只保留每一列的最大值，那么空间的利用率就可以得到提高。

Java代码实现

public int greatestMiningGoldValue3(int n, int w, int[] g, int[] p) {
    int[] maxMiningGold = new int[w + 1];
    for (int i = 1; i <= n; i++) {
        for (int j = w; j >= 0; j--) {
            if (j >= p[i - 1])
                maxMiningGold[j] = Math.max(maxMiningGold[j], maxMiningGold[j - p[i - 1]] + g[i - 1]);
        }
    }
    System.out.println(Arrays.toString(maxMiningGold));
    return maxMiningGold[w];
}