问题描述：
有n 个物品，它们有各自的重量和价值，现有给定容量的背包，如何让背包里装入的物品具有最大的价值总和？
解决这个题有两种方法，和其它的动态规划问题一样
数组w[]为物品的重量，v[]为物品的价值
一种是递归的思想，从后向前考虑，背包决定是否放一个物品是根据两个值的大小判断（一个值是背包没有放入这个物品的价值，另一个值是背包放入这个物品，另外背包容量减少物品重量的价值），去两个值中的最大值，递归结束条件是物品放完或者是背包容量小于等于0。
dp
接下来就是动态规划的思想，动态规划是从前往后想
求这个背包问题首先要画一个表
横轴是容量，纵轴是物品id
求解问题的过程就是维护这个表的过程，求解的值，就是最后一个空格的值
首先对于第0号物品
容量为0时，由于自身重量为1，所以放不进去，所以空格填0，容量为1以后，该物品可以放进去了，就都为6
对于第1号物品
对于（2,1）这个位置，由于背包容量是2，所以我可以放1号物品，将0号物品拿出来，或者不放1号物品，判断两种情况下的最大值，是第一种情况。
对于（3,1）这个位置，背包容量为3，可以1,0两个物品都放，或者保持（2,1），结果两个都放是最大值。
对于第2号物品
（3,2）这个位置是（0,1）+2号物品的价值和（3,1）比大小，结果是（3,1）比较大，所以还是16
（4,2）这个位置是（1,1）+2号物品的价值和（4,1）比大小，结果是（1,1）+12大，所以为18
（5,2）这个位置是（2,1）+2号物品的价值和（5,1）比大小，结果是（2,1）+12大，所以为22
所以最后背包的最大值为22
package action; public class demo { public static void main(String[] args) { int size = 5; int[] w = { 1, 2, 3 }; int[] v = { 6, 10, 12 }; System.out.println(backpack(w, v, size)); } public static int backpack(int[] w, int[] v, int size) { if (w.length != v.length) return -1; int n = w.length; if (n == 0) return 0; int[][] memo1 = new int[n][size + 1]; for (int i = 0; i <= size; i++) { memo1[0][i] = (i >= w[0] ? v[0] : 0); } for (int i = 1; i < n; i++) { for (int j = 0; j <= size; j++) { memo1[i][j] = memo1[i - 1][j]; if (j >= w[i]) { memo1[i][j] = Math.max(memo1[i][j], v[i] + memo1[i - 1][j - w[i]]); } } } return memo1[n - 1][size]; } }
