问题概述：
有一位国王拥有5座金矿，每座金矿的黄金储量不同，
需要参与挖掘的工人人数也不同。例如有的金矿储量是500kg黄金，需 要5个工人来挖掘；有的金矿储量是200kg黄金，需要3个工人来挖 掘…… 如果参与挖矿的工人的总数是10。每座金矿要么全挖，要么不挖，不能 派出一半人挖取一半的金矿。要求用程序求出，要想得到尽可能多的黄 金，应该选择挖取哪几座金矿？
什么是动态规划：
动态规划：将复杂问题简化为规模较小的子问题，再从简单的子问题自底向上一步一步递推，最终得到复杂问题的最优解
思路：
利用动态规划思想将大问题拆分为一个个小问题，之后一步一步解决问题
例：
如此直至人数为0或者剩余金矿数为0,也就是问题的边界
之后自底向上就可以从小问题的最优解求出整体的最优解，使利益最大化
具体解释与步骤详情参考代码
package algorithm;
/**
* 动态规划金矿问题
* 如何在已有人数和金矿收益情况下获得最大的淘金收益
* 动态规划：将复杂问题简化为规模较小的子问题，
* 再从简单的子问题自底向上一步一步递推，最终得到复杂问题的最优解
* 动态规划的要点：
* 确定全局最优解与最优子结构间的关系
* 确定问题的边界
*/
public class GoldMining {
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(g.length,w,p,g));
System.out.println("最优收益为："+getBestGoldMining2(g.length,w,p,g));
System.out.println("最优收益为："+getBestGoldMining3(g.length,w,p,g));
}
/**
* 此方法采用递归方式计算每种最优子结构的收益情况，递归到问题的边界即可用人数为0，或者剩余矿数为0
* 缺点：
* 会进行许多的重复计算，每次都分2种最优子结构，时间复杂度为O(2^n)
* @param n 总金矿数
* @param w 总可用人数
* @param p 每个金矿需要人数
* @param g 每个金矿的收益
*/
public static int getBestGoldMining(int n,int w,int[] p,int[] g){
if(w==0 || n==0){
return 0;
}
//如果当前可用人数不足以挖当前矿，则换个矿,n-1代表当前矿
if(w<p[n-1]){
return getBestGoldMining(n-1,w,p,g);
}
/**
* 如果当前矿可以挖，则选取两个最优子结构（挖当前矿，不挖当前矿）中收益高的方法
* n-1 代表除去当前矿，去后一个矿查看
* w-p[n-1] 代表挖当前矿后剩下的人数
*/
return Math.max(getBestGoldMining(n-1,w,p,g),(getBestGoldMining(n-1,w-p[n-1],p,g)+g[n-1]));
}
/**
* 根据自底向上求解的步骤，采用一张表记录计算结果，避免重复计算
* 时间与空间复杂度都是O(n*w)
* @param n
* @param w
* @param p
* @param g
*/
public static int getBestGoldMining2(int n,int w,int[] p,int[] g){
//使用二维数组表示表，纵轴是金矿信息，横轴是人数信息
int[][] resultTable = new int[n+1][w+1];
//填充表格
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= w; j++) {
//当前人数不足以挖g[i-1]矿，就把获得收益置为不挖当前矿的收益
if(j<p[i-1]){
resultTable[i][j] = resultTable[i-1][j];
}else{
/**
* 可以挖当前矿，取挖矿与不挖矿的最优解
* resultTable[i][j]就代表当前矿的最大收益 = max(不挖当前矿去查看之后的收益，挖当前矿查看之后的收入并加上当前矿的收入)
* 为什么resultTable[i][j]后面的却是resultTable[i-1][j-p[i-1]]+g[i-1]
* 因为当前循环是从1开始的，g中的i-1、p中的i-1都其实代表的是当前矿的信息
*/
resultTable[i][j] = Math.max(resultTable[i-1][j],resultTable[i-1][j-p[i-1]]+g[i-1]);
}
}
}
//最后一个格子就是最优收益
return resultTable[g.length][w];
}
/**
* 以上方法的空间复杂度仍有可以优化的余地
* 根据Math.max(resultTable[i-1][j],resultTable[i-1][j-p[i-1]]+g[i-1]);我们可以发现我们当前的最优解都是根据上一行推导而来
* 故我们可以只用一行表格来代替整个表格，可以看出每次都是i-1使用左边的数据，所以我们从右边替换数据即可
* 以下代码我们相当于明面只保留了人数的横坐标，实际用两重for循环保证了还是二维的表格，只是节省了空间
*/
public static int getBestGoldMining3(int n,int w,int[] p,int[] g){
int[] resultTable = new int[w+1];
for (int i = 1; i <= n; i++) {
for (int j = w; j >=1; j--) {
if(j>=p[i-1]){
//左边的resultTable[j]是i号金矿时的收益，而右边则相当于是i-1号矿收益因为还未被覆盖
resultTable[j] = Math.max(resultTable[j],resultTable[j-p[i-1]]+g[i-1]);
}
}
}
return resultTable[w];
}
}