笔者心得

0-1背包问题一直是笔者的心头大患，从第一次接触到现在做了三四遍了，愣是感觉有点不能熟练掌握，所有你大可不必因为一次做得难受而烦恼，大家都一样哦。😝
下面笔者力求用最简洁的语言与代码来解决这个问题。

解题思路

设共有len件物品，重量数组为weight[],价值容量为value[],背包容量为V(注意这里是大写的“V”)。

先写表达式：

dp[i][v] = Math.max(dp[i-1][v],dp[i-1][v-weight[i-1]]+value[i-1]);

关于表达式

我们用dp[i][v]来表示将前i件物品装入容量为v(注意这里是小写的“v”)的背包所获得的最大价值，那么它可以由两个状态转移而来，其一是dp[i-1][v],表示没有装第i件物品，还有则是dp[i-1][v-weight[i]]+value[i],这里与上面表达式下标不同，只是因为使用了weight[0]与value[0]表示第一件物品，那么weight[i-]与value[i-1]则表示第i件物品。

上面表达式还有一点则是dp[i-1][v-weight[i]]+value[i],很多同学不理解数组后半部分为什么要用v-weight[i]，只用v，即将前i物品装入容量为v的背包获得的价值=将前i-1件物品装入容量为v的背包可以获得的价值+物品i的价值。假设我们总共5件物品，只能装入容量为8的背包两件，而可以装入容量为6的背包一件，这显然是不等价的。

关于循环

for(int i=1;i<=len;i++) {
            for(int v=weight[i-1];v<=V;v++){...}
}

笔者一直对第二层循环很纠结，首先由于v表示容量，我们很少写这样的循环，这里由于容量都是整数，而且我们转移方程需要不同容量的背包，因此我们需要计算对于不同容量的背包装入前i件物品所获得的最大价值，当然这里v不能从1开始，因为我们的转移方程需要v-weight[i],而且将前1件物品装入容量需求比它所需要的容量更小的背包是不实际的。

附代码

public static void main(String[] args) {
        int weight[] = {3,5,1,2,2};
        int value[] = {4,5,2,1,3};
        
        int V =8;
        System.out.println(Bag_01(weight, value, V));
    //  System.out.println(Bag_01_2(weight, value, V));
    } 
    public static int Bag_01(int weight[],int value[],int V) {
        int len = weight.length;
        int res =0;
        int dp[][] = new int[len+1][V+1];
        for(int v=0;v<=V;v++) {
            //将前0件物品装入容量为v的背包所获得的最大价值
            dp[0][v] =0; 
        }
        
        for(int i=1;i<=len;i++) {
            for(int v=weight[i-1];v<=V;v++) {
                dp[i][v] = Math.max(dp[i-1][v],dp[i-1][v-weight[i-1]]+value[i-1]);
                
            }
            System.out.println("\n");
        }
        for(int i=1;i<=len;i++) {
            if(dp[i][V]>res)
                res = dp[i][V];
        }
        return res;
    }