当前位置: 首页 > >

小灰算法--如何求解金矿问题

发布时间:

???????题目:
???????很久很久之前,有一个人拥有5座金矿,每座金矿的*鸫⒘坎煌枰斡胪诰虻娜耸膊煌缬械幕*鸫⒘渴500KG*穑枰5个工人挖掘,(200kg/3人,300kg/4人,350kg/3人,400kg/5人,500kg/5人)
???????如果参与挖矿的总数为10,每座金矿要么全挖,要么不挖,用程序求出,应该挖取那几座金矿。
???????
???????
???????
???????到了现在自己好好思考一下自己的思路。。。
???????
???????
???????
???????
???????解题思路:(典型的动态规划,和背包问题类似)
???????先假设最后一个金矿注定不会被挖掘
???????然后其余的金矿依次类推,当工人或者金矿为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]),
???????代码如下:


public class getBestGoldMining {
public static int getBestGoldMining(int w,int n,int[] p,int[] g){
if(w == 0 || n == 0){
return 0;
}
if(w return getBestGoldMining(w,n-1,p,g);
}
return Math.max(getBestGoldMining(w,n-1,p,g),getBestGoldMining(w-p[n-1],n-1,p,g) +g[n-1]);
}

public static void main(String[] args){
int w = 10;
int[] p = {5,5,3,4,3};
int[] g = {400,500,200,300,350};
System.out.println("最优收益"+getBestGoldMining(w,g.length,p,g));
}
}


???????以上算法虽然可以求解出最优解,但是时间复杂度太高为O(2^n)。用debug模式就可以看出许多方法调用是重复的,因此,我们应该避免这些重复调用。
???????这就要了解动态规划中的自底而上求解。
???????最后程序只需要保存一行数据,从右向左统计,把旧的数据一个一个的替换掉。
//通过二维数组列表计算。

代码如下:时间复杂度为o(n)


public static int getBestGoldMiningV3(int w,int[] p,int[] g){
int[] results = new int[w+1];
for(int i=1;i<=g.length;i++){
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];
}



友情链接: