【动态规划】01背包问题（滚动数组 + 手画图解）-Toy模板网

这篇具有很好参考价值的文章主要介绍了【动态规划】01背包问题（滚动数组 + 手画图解）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

01背包除了可以用形象的二维动态数组表示外，还可以使用空间复杂度更低的一维滚动数组。

文章目录

前言

一、滚动数组的基本理解

二、确定dp及其下标含义

三、确定递推公式

四、确定初始化

五、确定遍历顺序

1.用物品（正序）遍历背包（正序）

实现代码：

手写图解：

2.用背包（正序）遍历物品（正序）

实现代码：

手写图解：

3.用物品（正序）遍历背包（逆序）

实现代码：

手写图解：编辑

总结

前言

晦涩难懂的滚动数组，有两个非常重要的点：①倒序②物品嵌套背包遍历

一、滚动数组的基本理解

我对于滚动数组的理解是：

滚动数组是基于二维数组之上产生的，之所以滚动数组能够用一维的方式去完成和二维同样的工作，原因就是在于这个滚动数组能够重复产生数据，进而有“滚动”的效果。

滚动数组的本质还是二维数组，只是数据不再产生新的行，只在一行上一直进行数据的覆盖更新，因此要特别注意数据污染的情况。

二、确定dp及其下标含义

由题意与我们将要创建的一维数组可知，dp[j]的含义是：背包容量为j时能装的最大价值。

三、确定递推公式

与二维dp数组相同，dp[j]的状态可以由两种状态得来：

①拿第i件物品（拿了以后，背包容量会减，价值会增加）；

②不拿第i件物品；

所以可得：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

四、确定初始化

由递推公式可得：dp[j]是由它之前的数据得来的，也即想要知道dp[j]的数值，就需要知道dp[j-x]的数据。（x是往前推的、未定的下标）

所以初始化只需要初始化dp[0]为0即可。（目前分析来说）

五、确定遍历顺序

与二维数组相同的是，一维dp数组仍然需要遍历物品和背包容量两种变量，只有这样才能模拟出将物品放入背包的过程。

1.用物品（正序）遍历背包（正序）

实现代码：

for (int j = 0; j < bagCapacity; j++)
    {
        for (int i = 0; i < weight.size(); i++)
        {
            // 背包容量够放
            if (j >= weight[i])
            {
                dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
            }
            // 不够放
            else
            {
                dp[j] = dp[j];
            }
        }
    }

手写图解：

【动态规划】01背包问题（滚动数组 + 手画图解）

由此我们可以很明显地看出在一维dp数组的情况下，数据覆盖的时候会发生污染，发现了物品0被放进dp[2]两次。

难道是遍历前后顺序不对？

2.用背包（正序）遍历物品（正序）

实现代码：

for (int i = 0; i < weight.size(); i++)
        {
            for (int j = 0; j < bagCapacity; j++)
            {
            // 背包容量够放
            if (j >= weight[i])
            {
                dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
            }
            // 不够放
            else
            {
                dp[j] = dp[j];
            }
        }

手写图解：

【动态规划】01背包问题（滚动数组 + 手画图解）

交换后，还是不可避免地发生了数据污染。

由此我们可以知道：

正序遍历的时候会将上一个物品装进背包两回，导致错误，而逆序就可保证dp[j]不受前面数据的影响（这时前面的数据仍然都是0），也就保证了每件物品只被放进去一次。

分析到这，我们也可以知道：初始化必须让整个dp数组的值都初始化为0（后面的dp[j]不能受前面数据的影响）。

3.用物品（正序）遍历背包（逆序）

实现代码：

for (int i = 0; i < weight.size(); i++)
    {
        for (int j = bagCapacity; j >= 0; j--)
        {
            // 背包容量够放
            if (j >= weight[i])
            {
                dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
            }
            // 不够放
            else
            {
                dp[j] = dp[j];
            }
        }
    }