例：
有一个国家发现了5座金矿，每座金矿的黄金储备量不同，需要参与的挖掘的工人数也不同。参与挖掘工人总数是10人。每座金矿要么全挖要么不挖，不能派出一半人挖取一半金矿。求解要得到尽可能多的黄金，应该挖取哪几座金矿？比如5座金矿总量和用工数如下：400金/5人，500金/5人，200金/3人，300金/4人，350金/3人
**0/1背包DP-金矿问题 - 图1

递推实现

dp[3][8] = max(dp[2][8], dp[2][5] + G[3])
dp[i][j] = max (dp[i-1][j], dp[i-1][j-P[i-1]] + G[i])

  1. public class Gold{
  2.     /**
  3.      * 获得金矿最优受益
  4.      * @param: w   工人数量
  5.      * @param: n   可选金矿数量
  6.      * @param: p[] 金矿开采所需的工人数量
  7.      * @param: g[] 金矿储量
  8.      */
  9.     public static void main(String[] args) {
  11.         int w=10;
  12.         int[] p={5,5,3,4,3};
  13.         int[] g={400,500,200,300,350};
  14.         System.out.println("最优受益:"+getBestGoldMining(w,p,g));
  15.     }
  16.     private static int getBestGoldMining(int w, int[] p, int[] g) {
  17.         //1、创建二维数组
  18.         int[][] dp=new int[g.length+1][w+1];
  19.         //填充表格
  20.         //代码中有两层循环第一个 for 循环每座金矿的储量
  21.         //按照一行一行循环，对于二维数组
  22.         for (int i=1;i<g.length+1;i++){ //第二个 for 循环工人数
  23.             for (int j=1;j<w+1;j++){
  24.                 if (j<p[i-1]){  //当前这座金矿不满足开采人数时，那么把当前值的前一个位置的值赋给当前值
  25.                     dp[i][j]=dp[i-1][j];
  26.                 }else {  //满足开采人数
  27.                     dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-p[i-1]]+g[i-1]);
  28.                 }
  29.             }
  30.         }
  31.         return dp[g.length][w];
  32.     }
  33. }