当前位置: 首页 > >

面试题之 【挖金矿问题】

发布时间:

1 题目

有一个国家发现了5座金矿,每座金矿的*鸫⒘坎煌枰斡胪诰虻墓と耸膊煌2斡胪诳蠊と说淖苁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=0w,则F(1,w)=0w=0w>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];
}


算法复杂度分析
时间复杂度并没有降低,但是空间复杂度降低了,这里使用的是一个一维数组,所以空间复杂度变成了O(w)



友情链接: