代码随想录|二维数组的01背包问题，优化-一维数组的01背包问题

二维数组的01背包问题

1.确定dp数组以及下标的含义

对于背包问题，有一种写法， 是使用二维数组，即dp[i][j] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。

2.确定递推公式

不放物品i：由dp[i - 1][j]推出，即背包容量为j，里面不放物品i的最大价值，此时dp[i][j]就是dp[i - 1][j]。

放物品i：dp[i - 1][j - weight[i]] + value[i] （物品i的价值），就是背包放物品i得到的最大价值

递归公式： dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

3.dp数组如何初始化

关于初始化，当背包容量为0时，dp[i][0]都是0（就是无论选取哪些物品背包价值总和一定是0）；

dp[0][j]:i=0，存放编号0的物品时，各个容量的背包所能存放的最大价值

很明显当j

很明显当j=weight[0]时，dp[0][j]应该是value[0]，因为背包容量足够放编号0物品

代码实现

package Bag;
 
/**
 * @author joyyiyi-3
 * @version 1.0
 * @date 2023/9/8 23:44
 */
public class BagProblem {
    public static void main(String[] args) {
        int[] weight={1,3,4};
        int[] value={15,20,30};
        int bagSize=4;
        testWeightBagProblem(weight,value,bagSize);
    }
    public  static  void testWeightBagProblem(int[] weight,int[] value,int bagSize){
        //创建dp
        int goods=weight.length;//获取物品 的数量
        int[][] dp=new int[goods][bagSize+1];
        //初始化dp
        for(int j=weight[0];j<=bagSize;j++){
            dp[0][j]=value[0];
        }
        //
        for(int i=1;i<weight.length;i++){//遍历物品的重量
            for(int j=1;j<=bagSize;j++){//遍历背包大小
                if(j<weight[i]){
                    //当前背包容量都没有当前物品i大的时候，不放物品i
                    //那么钱i-1个物品能放下的最大价值就是当前情况的最大价值
                    dp[i][j]=dp[i-1][j];
                }
                else{
                    //当前背包容量可以放下物品i,但我们要考虑是放物品i还是不放物品i的价值最大
                    dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i]);
                }
            }
        }
 
    }
}

优化-一维数组的01背包问题

1.确定dp数组的定义

在一维dp数组中，dp[j]表示：容量为j的背包，所背的物品价值可以最大为dp[j]。

2.一维dp数组的递推公式

dp[j]为 容量为j的背包所背的最大价值，那么如何推导dp[j]呢？

dp[j]有两个选择，一个是取自己dp[j] 相当于 二维dp数组中的dp[i-1][j]，即不放物品i，一个是取dp[j - weight[i]] + value[i]，即放物品i，指定是取最大的，毕竟是求最大价值，

所以递归公式为：

dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

 3.一维dp数组如何初始化

dp[j]表示：容量为j的背包，所背的物品价值可以最大为dp[j]，那么dp[0]就应该是0，因为背包容量为0所背的物品的最大价值就是0。 

4.一维dp数组遍历顺序

和二维dp的写法中，遍历背包的顺序是不一样的！

二维dp遍历的时候，背包容量是从小到大，而一维dp遍历的时候，背包是从大到小。

为什么呢？

倒序遍历是为了保证物品i只被放入一次！。但如果一旦正序遍历了，那么物品0就会被重复加入多次！

1.首先倒序看看

我对 for(int i=0;i=weight[i];j--){}}这个顺序进行遍历：

i=0，j=4，3，2，1

得到的dp：【0，15，15，15，15】

i=1，j=4，3

得到的dp：【0，15，15，20，35】

i=2，j=4

得到的dp：【0，15，15，20，35】

2.其次正序看看

我对 for(int i=0;i

i=1，j=1，2，3，4

得到的dp：【0，15，30，45，60】

这里就可以看出来如果我们正序遍历的话，物品i会被重复放置，所以不可用正序遍历背包大小。

本质上还是一个对二维数组的遍历，并且右下角的值依赖上一层左上角的值，因此需要保证左边的值仍然是上一层的，从右向左覆盖。

3.两个for循环的顺序

再来看看两个嵌套for循环的顺序，代码中是先遍历物品嵌套遍历背包容量，那可不可以先遍历背包容量嵌套遍历物品呢？

不可以！

因为一维dp的写法，背包容量一定是要倒序遍历（原因上面已经讲了），如果遍历背包容量放在上一层，那么每个dp[j]就只会放入一个物品，即：背包里只放入了一个物品。

如果我对 for (int j=bagSize;j>=1;j--){for(int i=0;i

代码实现

package Bag;
 
/**
 * @author joyyiyi-3
 * @version 1.0
 * @date 2023/9/9 11:53
 */
public class BagProblem2 {
    public static void main(String[] args) {
        int[] weight={1,3,4};//物品重量
        int[] value={15,20,30};//物品价值
        int bagSize=4;
        testWeightBagProblem2(weight,value,bagSize);
    }
    public static void testWeightBagProblem2(int[] weight,int[] value,int bagSize){
        int wLen=weight.length;
        //定义dp，dp[j]表示背包容量为j时，能获得最大价值
        int[] dp=new int[bagSize+1];
        //遍历顺序，先物品再背包容量
        
        for(int i=0;i<wLen;i++){//先遍历物品
//这里j>=weight[i];是背包容量要能承载当前遍历的物品，否则当前背包就不行，不需要遍历
            for (int j=bagSize;j>=weight[i];j--){//再反序遍历背包大小
                dp[j]=Math.max(dp[j],dp[j-weight[i]]+value[i]);
            }
        }
        
    }
}
 
 
 

开发的面试问题

就是本文中的题目，要求先实现一个纯二维的01背包，如果写出来了，然后再问为什么两个for循环的嵌套顺序这么写？反过来写行不行？再讲一讲初始化的逻辑。

二维的dp的for循环的顺序可以反过来写，先遍历物品还是先遍历背包容量都无所谓

假设我们的for循环是先遍历物品，再遍历背包容量，那么初始化

首先dp[i][0]应为0，因为背包容量为0，能承载的价值自然为0

其次当j>=weight[0]时，dp[0][j]应该是value[0]，因为背包容量足够放编号0物品

然后要求实现一个一维数组的01背包，最后再问，一维数组的01背包，两个for循环的顺序反过来写行不行？为什么？

一维的dp的for循环顺序不可以反过来写，必须for循环先遍历物品再遍历背包（如果换了这个顺序，那么造成的结果是每个容量的背包只会被放入一个物品），而且需要倒序遍历背包（如果正序遍历背包的话一个物品会被放置多次）

注意以上问题都是在候选人把代码写出来的情况下才问的。