题目描述：01背包问题 w:重量 v：价值 cap：承重
1.递归解法：每一个物品都有取和不取两种决策，所以递归的时间复杂度为O(2^n)，两种决策所得到的价值分别为：maxValueRe(w, v, cap, n, curCap + w[index], index + 1) +v[index] 和maxValueRe(w, v, cap, n, curCap, index + 1))，取两种决策的结果的最大值即为最大价值。
2.备忘录解法：递归有很多重复计算，通过一个二维数组来存储递归的子问题的结果，简化计算。
3.自底向上（非递归写法）：与备忘录写法一样，只是换了一种方式，用循环。
4.滚动数组：优化非递归解法，因为当前子问题的结果只与上一个子问题的结果相关联，由result[i][j] = Math.max(result[i][j], result[i - 1][j- w[i]]+ v[i])可知，i只与i-1有关系，j不变，因此开辟的数组只需要一个只有两列的二维数组就可以了。
Talk is cheap,show me the code !!!
参考代码：
package Dp; import org.junit.Test; /** * 01背包问题 w:重量 v：价值 cap：承重 * * @author Tongkey */ public class Backpack { public int[][] result; /** * 递归解法，时间复杂度为O(2^n) * * @param w * 重量 * @param v * 价值 * @param cap * 承重 * @param n * 数量 * @param curCap * 当前的重量 总重量 = 当前的重量+剩余的重量 * @param index * 当前的下标值 * @return */ public int maxValueRe(int[] w, int[] v, int cap, int n, int curCap, int index) { if (curCap > cap) { return 0; } if (index >= n) { return 0; } return Math.max(maxValueRe(w, v, cap, n, curCap + w[index], index + 1) + v[index], maxValueRe(w, v, cap, n, curCap, index + 1)); } /** * 备忘录解法（自顶向下），时间复杂度O(n*cap),空间复杂度O(n*cap) * * @param w * 重量 * @param v * 价值 * @param cap * 承重 * @param n * 数量 * @param curCap * 当前的重量 总重量 = 当前的重量+剩余的重量 * @param index * 当前的下标值 * @return */ public int maxValueMemory(int[] w, int[] v, int cap, int n, int curCap, int index) { if (curCap > cap) { return 0; } if (index >= n) { return 0; } if (result[index][curCap] > 0) { return result[index][curCap]; } result[index][curCap] = Math .max(maxValueRe(w, v, cap, n, curCap + w[index], index + 1) + v[index], maxValueRe(w, v, cap, n, curCap, index + 1)); return result[index][curCap]; } @Test public void testMaxValueMemory(){ int[] w = { 42, 25, 30, 35, 42, 21, 26, 28 }; int[] v = { 261, 247, 419, 133, 391, 456, 374, 591 }; int n = 8; int cap = 297; result = new int[n][cap + 1]; int maxValueRe = maxValueMemory(w, v, cap, n, 0, 0); System.out.println(maxValueRe); System.out.println("----------------------"); } /** * 自底向上（非递归写法）,时间复杂度O(n*cap),空间复杂度O(n*cap) * * @param w * @param v * @param cap * @param n * @param curCap * @param index * @return */ public int maxValueDp(int[] w, int[] v, int cap, int n, int curCap, int index) { result[0][0] = 0; // 第一行 for (int i = 1; i <= cap; i++) { if (i >= w[0]) result[0][i] = v[0]; } // 第一列 for (int i = 1; i < n; i++) { result[i][0] = 0; } for (int i = 1; i < n; i++) { for (int j = 1; j <= cap; j++) { // 默认值，不取index当前的重量值 result[i][j] = result[i - 1][j]; if (j >= w[i]) result[i][j] = Math.max(result[i][j], result[i - 1][j - w[i]] + v[i]); } } return result[n - 1][cap]; } /** * 自底向上（利用滚动数组非递归写法优化）,时间复杂度O(n*cap),空间复杂度O(cap) * @param w * @param v * @param cap * @param n * @param curCap * @param index * @return */ public int maxValueDpMod(int[] w, int[] v, int cap, int n, int curCap, int index) { result[0][0] = 0; // 第一行 for (int i = 1; i <= cap; i++) { if (i >= w[0]) result[0][i] = v[0]; } for (int i = 1; i < n; i++) { for (int j = 1; j <= cap; j++) { result[i % 2][j] = result[(i - 1) % 2][j]; if (j >= w[i]) result[i % 2][j] = Math.max(result[i % 2][j], result[(i - 1) % 2][j - w[i]] + v[i]); } } return Math.max(result[0][cap], result[1][cap]); } /** * 把二维数组优化为一维数组版本 * @param w * @param v * @param n * @param cap * @return */ public int maxValueDp2(int[] w, int[] v, int n, int cap) { // 给定物品的重量w价值v及物品数n和承重cap int[] d = new int[cap + 1]; for (int i = 0; i < n; i++) { for (int j = cap; j >= w[i]; j--) { d[j] = Math.max(d[j], d[j - w[i]] + v[i]); } } return d[cap]; } @Test public void testMaxValueRe() { int[] w = { 42, 25, 30, 35, 42, 21, 26, 28 }; int[] v = { 261, 247, 419, 133, 391, 456, 374, 591 }; int n = 8; int cap = 297; result = new int[2][cap + 1]; int maxValueRe = maxValueDpMod(w, v, cap, n, 0, 0); System.out.println(maxValueRe); System.out.println("----------------------"); } }