从二维数组到一维数组——探索01背包问题的动态规划优化

文章目录

• 题目
• 前知
• • 背包问题
• 二维dp数组
• • 一、思路
  • 二、解题方法
  • 三、Code
• 一维dp数组
• • 一、思路
  • 二、解题方法
  • 三、Code
• 总结

本文将继续上一篇博客爬楼梯之后继续讲解同样用到了动态规划的 01背包问题

在解决动态规划问题时，我们经常面临着空间复杂度的挑战。01背包问题是一个典型的例子，通常使用二维数组来表示状态转移，但这样会带来额外的空间开销。在本文中，我们将探讨如何通过优化空间复杂度，将01背包问题从二维数组降维到一维数组，以提高算法的效率和性能。

题目

有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。

前知

背包问题

01背包问题是一个经典的动态规划问题，通常用来解决如何在有限的背包容量下选择物品以获得最大价值的问题。问题的描述是：给定一组物品，每种物品都有自己的重量和价值，在限定的背包容量下，选择哪些物品放入背包可以使得背包内物品的总价值最大化，且不能超过背包的承重。背包问题有以下几种：

二维dp数组

一、思路

首先，我们使用动态规划来解决01背包问题。通常，我们会使用一个二维数组dp[i][j]来表示在前i个物品中，背包容量为j时的最大总价值。我们初始化dp数组为0，并通过状态转移方程来更新dp数组，最终得到dp[n][C]作为问题的解，其中n为物品个数，C为背包容量。

二、解题方法

动规五部曲

1. 确定dp数组及下标i的含义：从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是dp[i][j] ，如下图所示：
   

2. 确定递推公式：dp[i][j]可以由两个方向推出，要么是放i，要么就不放i，递推公式为： dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

• 不放物品i时：里面的最大价值实际上是dp[i - 1][j]，因为此时代表已经达到背包最大容量时的最大价值，和上一层状态相同，当物品i的重量大于背包j的重量时，物品i无法放进背包中，所以背包内的价值依然和前面相同。
• 放物品i时：现在里面已经放了i，最大价值所以肯定有 value[i])，dp[i - 1][j - weight[i]]代表的是放物品i并且剩余空间能够刚好放下物品i时的最大价值

3. dp数组如何初始化：如果背包容量j为0的话，即dp[i][0]，无论是选取哪些物品，背包里面都放不下物品，背包价值总和一定为0，如图：
   再由递推公式可以看出dp[i][j]一定是由dp[i-1]得出的，所以还需要初始化最上面一层的dp数组，也就是dp[0][j]：存放编号0的物品的时候，各个容量的背包所能存放的最大价值。当最小的背包容量j连一个物品都存不下的时候，那么就让dp[0][j]=0，例如题目中把物品0的重量改为2，dp[0][1]就为0。如果背包能放得下物品的时候，dp[0][j] 应该是value[0],并且都是所有容量的都为value[0]，因为01背包问题，物品只能取一次，如图：
   

for (int j = 0 ; j < weight[0]; j++) {  // 当然这一步，如果把dp数组预先初始化为0了，这一步就可以省略，但很多同学应该没有想清楚这一点。
    dp[0][j] = 0;
}
// 正序遍历
for (int j = weight[0]; j <= bagweight; j++) {
    dp[0][j] = value[0];
}

其它非0下标的dp数组都可以初始化为0，因为都是由上面一层或左上方推出来的，0会被覆盖掉

4. 确定遍历顺序：从递推公式 dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);可以看出，有两个for循环遍历方向得到dp数组，一个是物品，另一个是背包容量，由于dp[i][j]所需要的数据就是左上角，所以先遍历物品还是先遍历背包容量都没什么太大问题

先遍历物品，再遍历背包容量，一行一行遍历：

先遍历背包容量，再遍历物品，一列一列遍历：

5. 举例推导dp数组：最终结果dp[2][4]
   

三、Code

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);
    }

    /**
     * 动态规划获得结果
     * @param weight  物品的重量
     * @param value   物品的价值
     * @param bagSize 背包的容量
     */
    public static void testWeightBagProblem(int[] weight, int[] value, int bagSize){

        // 创建dp数组
        int goods = weight.length;  // 获取物品的数量
        int[][] dp = new int[goods][bagSize + 1];

        // 初始化dp数组
        // 创建数组后，其中默认的值就是0
        for (int j = weight[0]; j <= bagSize; j++) {
            dp[0][j] = value[0];
        }

        // 填充dp数组
        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
                     * 那么此时分两种情况：
                     *    1、不放物品i
                     *    2、放物品i
                     * 比较这两种情况下，哪种背包中物品的最大价值最大
                     */
                    dp[i][j] = Math.max(dp[i-1][j] , dp[i-1][j-weight[i]] + value[i]);
                }
            }
        }

        // 打印dp数组
        for (int i = 0; i < goods; i++) {
            for (int j = 0; j <= bagSize; j++) {
                System.out.print(dp[i][j] + "\t");
            }
            System.out.println("\n");
        }
    }
}

一维dp数组

一、思路

使用二维数组会带来额外的空间开销。为了优化空间复杂度，我们可以通过滚动数组将二维数组降维为一维数组。我们定义一个一维数组dp[j]，其中dp[j]表示背包容量为j时的最大总价值。然后，我们先从前往后遍历物品，再通过逆序遍历背包容量dp数组来更新状态，最终得到dp[C]作为问题的解。这样，我们成功将空间复杂度从O(n*C)降低到了O(C)，大大提高了算法的效率和性能。

二、解题方法

把dp[i - 1]那一层拷贝到dp[i]上，对状态进行压缩，只用一个dp[j]滚动数组

动规五部曲

1. 确定dp数组及下标i的含义：容量为j的背包，所背的物品价值可以最大为dp[j]

2. 确定递推公式：一维dp数组相对于二维dp数组的写法，就是把dp[i][j]中i的维度去掉了。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数组如何初始化：当背包容量为0时，所背的物品价值dp[0]最大就是0，dp数组非0下标都让值为1，这样在递推之后，取到的最大值就会是递推过程中的最大值，而不会被其它初始值给覆盖掉

4. 确定遍历顺序：根据递推公式得出同样有两个方向，首先从前到后遍历物品，再倒序遍历背包容量，这个顺序不能像二维dp数组一样调换顺序。

• 如果是先倒序遍历背包容量，再正序遍历物品的话，那么里面的for循环会重复从第一个物品开始遍历，就只会在背包里添加一个物品。
• 如果是先从前到后遍历物品，再正序遍历背包容量的话，物品0就不止添加了一次，而会被重复添加，从后向前遍历的话，前面的状态就不会被后面所调用到。
  正序：dp[1] = dp[1 - weight[0]] + value[0] = 15
  dp[2] = dp[2 - weight[0]] + value[0] = 30
  倒序：dp[2] = dp[2 - weight[0]] + value[0] = 15 （dp数组已经都初始化为0）
  dp[1] = dp[1 - weight[0]] + value[0] = 15
• 二维dp数组遍历的时候不用倒序是因为对于二维dp，dp[i][j]都是通过上一层即dp[i - 1][j]计算而来，本层的dp[i][j]并不会被覆盖

for(int i = 0; i < weight.size(); i++) { // 遍历物品
    for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
        dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

    }
}

5. 举例推导dp数组：用题目进行举例
   

三、Code

    public static void main(String[] args) {
        int[] weight = {1, 3, 4};
        int[] value = {15, 20, 30};
        int bagWight = 4;
        testWeightBagProblem(weight, value, bagWight);
    }

    public static void testWeightBagProblem(int[] weight, int[] value, int bagWeight){
        int wLen = weight.length;
        //定义dp数组：dp[j]表示背包容量为j时，能获得的最大价值
        int[] dp = new int[bagWeight + 1];
        //遍历顺序：先遍历物品，再遍历背包容量
        for (int i = 0; i < wLen; i++){
            for (int j = bagWeight; j >= weight[i]; j--){
                dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
            }
        }
        //打印dp数组
        for (int j = 0; j <= bagWeight; j++){
            System.out.print(dp[j] + " ");
        }
    }

总结

通过这篇博客，读者可以清晰地了解如何通过优化空间复杂度，将01背包问题的动态规划解法从二维数组降维到一维数组，并且可以对比二者在性能上的差异，从而更好地掌握这一知识点。希望本文能够帮助读者更好地理解和应用动态规划算法在01背包问题中的使用，如果有任何疑问或者建议，欢迎留言讨论