金矿问题题目
很久很久以前，有一位国王拥有5座金矿，每座金矿的黄金储量不同， 需要参与挖掘的工人人数也不同。例如有的金矿储量是500kg黄金，需要5个工人来挖掘；有的金矿储量是200kg黄金，需要3个工人来挖掘…… 如果参与挖矿的工人的总数是10。每座金矿要么全挖，要么不挖，不能 派出一半人挖取一半的金矿。要求用程序求出，要想得到尽可能多的黄金，应该选择挖取哪几座金矿？
解题思路
首先分析题意得出这是一个动态规划问题，所谓动态规划就是把复杂的问题简化成规模较小的子问题，再从简单的子问题自底向上一步一步递推，最终得到复杂问题的最优解。
动态规划的要点：
确定全局最优解和最优子结构之间的关系，以及问题的边界。这个关系用数学公式来表达的话，就叫作状态转移方程式 。
先找问题得边界：
一直把问题简化成在0个金矿或0个 工人时的最优选择，这个收益结果显然是0，也就是问题的边界 。
自底向上求解：
- 状态转移方程: n是当前金矿储量，w是当前金矿所需人数 ,p是挖掘金矿所需人数数组，g是金矿储量数组
- F(n,w) = F(n-1,w) (n>1,w<p[n-1])
- F(n,w) = max( F(n-1,w),F(n-1,w-p[n-1])+g[n-1]) (n>1,w>=p[n-1])
- 二维数组表示这张对应得表
递归求解代码
/*
* 获得金矿最优收益
* @param w 工人数量
* @param n 可选金矿数量
* @param p 金矿开采所需的工人数量
* @param g 金矿储量
*/
public static int getBestGoldMining(int w, int n,int[] p, int[] g){
if(w==0 || n==0){
return 0;
}
if(w<p[n-1]){
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)，在这个算法中有很多重复得调用计算动态规划代码
/**
* 获得金矿最优收益
* @param w 工人数量
* @param p 金矿开采所需的工人数量
* @param g 金矿储量
*/
public static int getBestGoldMiningV2(int w, int[] p, int[] g)
{
//创建表格
int[][] resultTable = new int[g.length+1][w+1];
//填充表格
for(int i=1; i<=g.length; i++){
for(int j=1; j<=w; j++){
if(j<p[i-1]){
resultTable[i][j] = resultTable[i-1][j];
}else{
resultTable[i]
[j] = Math.max(resultTable[i-1]
[j], resultTable[i-1][j-p[i1]]+ g[i-1]);
}
}
}
//返回最后1个格子的值
return resultTable[g.length][w];
}
//动态规划求解时间和空间都是是O(nw)代码优化
/**
* 获得金矿最优收益
* @param w 工人数量
* @param p 金矿开采所需的工人数量
* @param g 金矿储量
*/
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]);
}
}
}
//返回最后1个格子的值
return results[w];
}
在表格中除第1行之外，每 一行的结果都是由上一行数据 推导出来的。我们以4个金矿9个工 人为例。 4个金矿、9个工人的最优结果，是由它的两个最优子结构，也就是3个 金矿、5个工人和3个金矿、9个工人的结果推导而来的。这两个最优子 结构都位于它的上一行。 所以，在程序中并不需要保存整个表格，无论金矿有多少座，我们只保 存1行的数据即可。在计算下一行时，要从右向左统计（读者可以想想 为什么从右向左），把旧的数据一个一个替换掉。空间复杂度降低到了O(n)
