背包的最大容积为：8
dp[i][j]表示将前i件物品装进限重为j的背包可以获得的最大价值。
注：j表示的是当前背包的容积，即它还能容纳多少东西，而不是当前背包中物品的总体积。所以，随着物品的加入，j会减小，及容积减小。转移状态方程：
dp[i][j]=dp[i-1][j-w[i]]+v[i]的理解：
这种情况下，状态i是由状态i-1加了第i件物品得到的，那么体现出来就是，i-1状态时的背包容积减去第i件物品的体积即j-w[i]构成了状态i时的背包的总容积，（因为把第i件物品加进去了。背包的总容积要变小）。
而总价值就是要加上第i件物品的价值，即i-1状态时的总价值加上第i件物品的价值（+v[i]），构成了状态i时背包的总价值。
(1)
w[],v[]两个数组传入函数前未做处理
//w[],v[]两个数组传入函数前未做处理 int[] w={2,3,4,5}; int[] v={3,4,5,6}; int m=8;
1 //w[],v[]两个数组传入函数前未做处理 2 public static int findMaxValue(int[] w,int[] v,int m ){ 3 4 int line=w.length; 5 int row=m; 6 7 int[][] dp=new int[line+1][row+1]; 8 9 10 for(int i=1;i<line+1;i++){ 11 for(int j=1;j<row+1;j++){ 12 if(j<w[i-1]){ 13 dp[i][j]=dp[i-1][j]; 14 }else{ 15 dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-w[i-1]]+v[i-1]); 16 } 17 } 18 } 19 20 return dp[line][row]; 21 22 }
空间优化：
1 //滚动数组，优化空间 2 //w[],v[]两个数组传入函数前，均已经在第一位添加了0 3 public static int findMaxValue3(int[] w,int[] v,int m){ 4 int[] dp=new int[m+1]; 5 for(int i=0;i<w.length;i++){ 6 for(int j=m;j>=w[i];j--){ 7 dp[j]=Math.max(dp[j],dp[j-w[i]]+v[i]); 8 } 9 } 10 return dp[m]; 11 12 }
（2）
w[],v[]两个数组传入函数前，均已经在第一位添加了0
1 //w[],v[]两个数组传入函数前，均已经在第一位添加了0 2 int[] w1={0,2,3,4,5}; 3 int[] v1={0,3,4,5,6}; 4 int m1=8;
1 //w[],v[]两个数组传入函数前，均已经在第一位添加了0 2 public static int findMaxValue1(int[] w,int[] v,int m ){ 3 4 int line=w.length; 5 int row=m+1; 6 7 int[][] dp=new int[line][row]; 8 9 for(int i=1;i<line;i++){ 10 for(int j=1;j<row;j++){ 11 if(j<w[i]){ 12 dp[i][j]=dp[i-1][j]; 13 }else{ 14 dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]); 15 } 16 } 17 } 18 19 return dp[line-1][row-1]; 20 21 }
空间优化：
1 //滚动数组，优化空间 2 //w[],v[]两个数组传入函数前，均已经在第一位添加了0 3 public static int findMaxValue3(int[] w,int[] v,int m){ 4 int[] dp=new int[m+1]; 5 for(int i=0;i<w.length;i++){ 6 for(int j=m;j>=w[i];j--){ 7 dp[j]=Math.max(dp[j],dp[j-w[i]]+v[i]); 8 } 9 } 10 return dp[m]; 11 12 }