背包01问题（Java）

Question

为什么老是要和上一行进行比较？还有这两句代码语句有点不懂（能够详细的解释一下吗？）

 

public class Test {

    public static void main(String[] args){
        int w[] = {4,3,1};
        int p[] = {3000,2000,1500};   //1500是吉他，3000是音响，2000是电脑。
        int m = 4;   //表示的是背包的容量。
        int n = 3; //表示的意思是物品的个数。

        //创建一个二维数组
        int v[][] = new int[n+1][m+1];    //v[i][j]表示的意思是考虑钱i件物品，重量小于j的最大价值。
        /*
        * 为什么使用n+1和m+1？
        * 为了使数组下标从0到n，0到m。
        * */

        //初始化第一列和第一行都为0.
        for(int i=0;i<4;i++){
           v[i][0]=0;
        }
        for(int j=0;j<5;j++){
            v[0][j]=0;
        }
        //动态规划遍历,重新赋值。
        for(int i=1;i<4;i++){
            for(int j=1;j<5;j++){
                if(w[i-1]>j){
                    v[i][j] = v[i-1][j];
                }
                else{
                    v[i][j] =Math.max(v[i-1][j],p[i-1]+v[i-1][j-w[i-1]]);
                }
            }
        }
       

        //遍历，看看所有的情况。
        for(int i=0;i<4;i++) {
            for (int j = 0; j < 5; j++) {
                System.out.print(v[i][j]+" ");
            }
            System.out.println();

        }


    }
}

Answer 1

背包问题
前k个物品放入容量为M背包的最大价值可转化为前k-1个物体放入容量为M背包的问题
分两种情况考虑，不装第k种物品或至少装一件第k种物品
如果不装第k种物品，那么只能用前k-1种物品装入背包，而背包的重量限制仍然是M，在这种情况下，背包的最大价值是 F k-1（y）
如果k种物品装了一件，那么背包的价值是V k，且重量是M k，剩下的物品仍需要在前k种物品中选择（因为最优的装法可能包含多个第k种物品），于是问题归约在背包重量限制为y-m k的情况下如何使用前k种物品装入背包以取得最大价值F k（y-M k）

那么你题目中的比较就是
放入前i-1个物品的最大价值加上放入第i个物品的价值（即剩余容积能放入的最大价值），放入前i-1个物品的最大价值但不放入第i个物品的价值（剩余容积无法再放入），取两个值中的最大值，因为我们无法确定此时背包此时剩余的容量能否再放入第i个物品，以及选取何种物品能使背包剩余空间价值最大
为什么要比较 就是因为你要通过比较取得最优选择以得到最大价值