闲来无事，想到了自己对解动态规划问题掌握的还不大熟练，所以做个题练习下。
1，问题描述：
有一辆小船，能够承载的最高重量为c，当船承载的重量超过c时，船会沉没。 现在有n个物品，物品i的重量为w(i),价值为v(i)，应该如何选择装船的物品，保证船不沉，使得装上船的物品总价值最大?
2，问题分析：
这是一道0-1动态规划问题。对于动态规划问题，最重要的是找到递归方程。要找到递归方程f(x,y)，就要知道自变量x,y，因变量f。约束条件c一定是一个自变量，那么还有一个自变量呢，是w还是v呢，我们可以看见，w和v可以看成是关于n的函数，所以另一个自变量就是n。那么f(c，n)表示的含义为：在容量限制为c下，有n个商品情况下，能够取得的商品最大价值。
这里要注意的一点是：我们在程序中，f(c, n)的含义为，在重量限制为c，到选取第n个物品时，可以达到的最大价值。这是因为我们一般会从一个商品开始，而到了第n个商品，也代表会有n种不同的商品。
计算f（c，n）即取第n个物品求最大价值的时候，一定是先过了第n-1个物品来的。从n-1到n有两条路径
1，不取第n-1个物品而来。f(c, n-1)
2，取第n-1个物品而来。 f(c-w[n], n-1) + v[n]
递归方程为：
f(c, n) = max( f(c-w[n], n-1) + v[n], f(c, n-1))
其中：w[n]表示第n个物品的重量，v[n]表示第n个物品的价值。
3，喜闻乐见填表格
一般来说，动态规划都会填写最简单的表格数据，而这些数据，将会用于填充剩下的空白表格。
4，实验代码：
public class Test {private int c;private int n;private int[] w;private int[] v;private int[][] f;// f(x,y)表示在总重限制为x时，选取第y个物品，可以达到的最大价值。这里的选取条件是加入第y个物品，容量不超限制，且取得的价值最大。// 如果拿了第i个物品，那么相应的价值f(xxx, i)会比f(yyy, i-1)大，如果不变，说明不取第i个物品（这里假设的前提是物品的价值为正整数）// 这样就可以求出到底拿了哪些物品，以及价值的最大值。(最大值一定处于f矩阵的最右下角)private Test(int c, int[] w, int[] v) {this.c = c;this.n = w.length;this.w = new int[n + 1];this.w[0] = 0;System.arraycopy(w, 0, this.w, 1, n);// 使用第1为做为数组的开始this.v = new int[n + 1];this.v[0] = 0;System.arraycopy(v, 0, this.v, 1, n);// 使用第1为做为数组的开始this.f = new int[c + 1][n + 1]; //这里也可以是反的for (int[] ints : this.f) {for (int anInt : ints) {anInt = Integer.MIN_VALUE;// 全部初始化为最小值}}for (int i = 0; i < this.n + 1; i++) {this.f[0][i] = 0; //容量限制为0的情况下，最大价值总为0}}public void result() {for (int cc = 1; cc < c + 1; cc++) {//计算第nn件物品在每个容量限制下能取得的最大价值for (int nn = 1; nn < n + 1; nn++) {if (cc >= w[nn]) {// 当前容量cc是否可以存放第nn个物品f[cc][nn] = Math.max(f[cc - w[nn]][nn - 1] + v[nn], f[cc][nn - 1]);// 切分，这里是反着分析的，也就是到了计算取第nn个物品求最大价值的时候，// 则一定是先选过了第nn-1个物品来的。从nn-1到nn有两条路径// 1，不取第nn-1个物品而来。// 2，取第nn-1个物品而来。// 递归方程：// f(cc, nn) = Math.max(取第nn-1个物品而来, 不取第nn-1个物品而来) ==> f(cc, nn) = Math.max(f(cc-w[nn], nn-1) + v[nn], f(cc, nn-1))} else {f[cc][nn] = f[cc][nn - 1];// 如果第nn个物品要装不下了。则是从不取第nn-1个物品而来的}}}System.out.println("重量：" + Arrays.toString(w));System.out.println("价值：" + Arrays.toString(v));for (int i = 0; i < this.f.length; i++) {System.out.printf("容量限制为:%s的最大价值\t", i);for (int anInt : this.f[i]) {System.out.print(anInt + "\t");}System.out.println();}System.out.println("可以获利最大值为：" + this.f[c][n]);System.out.print("选取的物品编号为：");int cap = this.c;for (int i = n; i >= 1; i--) {if (f[cap][i] != f[cap][i - 1]) {// 这里找的是由于i物品的加入，导致的价值变化，cap -= w[i];//如果有变化，则表示选取了i物品，否则就是没有取i物品System.out.print(i + "\t");}}}public static void main(String[] args) {new Test(20, new int[]{20, 10, 5, 15}, new int[]{4, 3, 2, 1}).result();}}5，输出：
完成的表格为：
人工检验没问题。
