动态规划算法入门：什么是背包问题？

背包问题的固定背景

• 现有个容量为M的背包和N件物品
  • 第 iii 件物品的体积为 ViV_iVi​ ，价值为 WiW_iWi​
• 求背包能装下的最大价值

背包问题的分类

• 01背包

  每个物品只有一个（即只能选择一次）；

• 完全背包

  每个物品有无限个（可以重复选择）

• 多重背包

  每种物品为有限个，且数量不完全相同

• 分组背包

  按组打包，每组最多选一个物品

背包问题的求解

背包问题一般需要通过“动态规划”（Dynamic programming，简称Dp）的方式去求解问题，那我们先来了解什么是 “动态规划” 。

引入问题

• 现有个容量为M的背包和N件物品
  • 第 iii 件物品的体积为 ViV_iVi​ ，价值为 WiW_iWi​
• 每个物品只有一个（即只能选择一次）
• 求背包能装下的最大价值

这个问题实际上就是“01背包问题”。

题目的目标很明确：“要我们通过最小的空间取得最大的收益”，那我们是不是可以尝试用贪心算法来尝试求解呢？

尝试用贪心策略求解

首先我们用“密度”的思想，来算出每件物品的性价比，性价比 = 价值/体积；

我们按照物品的性价比进行排序，然后依次选择性价比最高的物品，感觉的确可以得到最优解！

但真的是这样吗？

我们来看一种情况：

背包体积为5，有4件物品，现已经按照物品的性价比进行降序排序。

物品编号	物品价值Wi	物品体积 Vi	物品性价比
1	2	1	2
2	4	2	2
3	4	3	1.33
4	4	5	0.8

按照贪心策略，我们肯定选择1-2号物品，当选3号物品的时候发现装不下了，便退出了选择。

但我们发现，实际上我们还有体积的浪费，我们完全可以用掉多余的空间去选择性价比低但价值更高的3号物品。贪心策略 出错了！

用动态规划求解

同样的问题，我们来看看动态规划是如何解决的。

设 dp[i][j] 的含义是：

在背包容量为 jjj 的前提下，从前 iii 个物品中选能够得到的最大价值。

不难发现，dp[N][M]就是本题答案。那么如何去计算呢？

我可以把dp[i][j] 分解为两个部分：

• 不选第i个物品

  即从前 i−1i-1i−1 个物品中选，总体积不超过 jjj ，对应 dp[i-1][j];

• 一定选第i个物品

  既然确定一定会选第 iii 个物品，那可以预留第 iii 个物品的空间和价值，然后从前 i−1i-1i−1 个物品去选。即 dp[i-1][j-v[i]] + w[i]

注意： 这一部分有可能是空集，因为会出现第 iii 个物品的体积超过背包容量，因此要先进行可行性判断。即if(j ≥ w[i])

最后，我们只需要求得两个部分的最大值即可，即

回到问题本身，我们尝试用动态规划求解：

1. 每一行的值都是从上一行的值为基础改变的。

2. 从绿色加粗的数字开始，值可能会发生变化。

   • 变化条件：

     上一行第 xxx 列的值（x=当前列索引−v[i]x = 当前列索引 - v[i] x=当前列索引−v[i]） 对应的值 小于 当前格子的值+w[i]当前格子的值+ w[i]当前格子的值+w[i]

   • 变化结果： 谁大留谁

3. 最后，最右下角的格子为最终答案。

求解代码与滚动数组优化

按照以上的思路则可以编写出下列求解代码：

• 时间复杂度：O(nm)O(nm)O(nm)

#include <iostream>
#include <algorithm>

using namespace std;

const int M = 1010;
int v[M], w[M];
int dp[M][M];

int main()
{
    int n, m;
    cin >> n >> m;

    for (int i = 1; i <= n; i++) cin >> v[i] >> w[i];

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            dp[i][j] = dp[i - 1][j];
            if (v[i] <= j)
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i]);
        }

    cout << dp[n][m] << endl;
    return 0;
}

使用滚动数组优化

不难发现，dp数组的 第 iii 行 的元素 仅由 第 i−1i-1i−1 行 的元素派生而来。与其我们把前一行拷贝到新一行，不如直接对前一行进行“更新”，便可把二维优化为一维。

去掉一维后，递推公式变为：

即

由此可见，我们由原先 从 111 遍历至 jjj 优化成了 从 w[i]w[i]w[i] 遍历至 mmm 。

但是，顺序真的对了吗？

回过头看这张表格，我们可以发现从绿色加粗的数字开始，我们都需要用到上一行的数据，但如果我们从小到大去遍历，我们要用的数据被更新掉了，那最后的值还会准确吗？

例如： 计算dp[2][4]的值，会用到dp[1][2]的值，但是在一维中dp[1][2]被刷新为dp[2][2]，最后得到的结果将会是8，这显然不对。

反之，我们从大到小进行遍历，就不会出现这样的问题了！被刷新的值之后都不会用上，完美符合我们的预期。

甚至最后，我们可以把w数组和v数组优化掉，变成边输入边计算：

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

int dp[N];

int main() {
    int n, m;
    cin >> n >> m;

    for (int i = 1; i <= n; i++) {
        int v, w;
        cin >> v >> w;
        for (int j = m; j >= v; j--)
            dp[j] = max(dp[j], dp[j - v] + w);
    }

    cout << dp[m] << "\n";

    return 0;
}

本文总结

动态规划的特点

1. 无后效性

   我们可以把解题过程以“行”为单位来看。我们求每一行的值都只跟上一行有关，与先前的值都无关。

   📌 严格定义： 如果给定某一阶段的状态，则在这一阶段以后过程的发展不受这阶段以前各段状态的影响。

2. 最优子结构

   在dp[i][j]中，就已经蕴含了“最优”的概念，利用这一小部分的“最优”。而大问题的最优解可以由小问题的最优解推出，这个性质即“最优子结构性质”。

动态规划与贪心策略的区别

背包问题算是个“二维的”问题，我不但要考虑体积，还要考虑价值，那这就涉及了一个 “性价比” 的问题。

• 一件物品的价值高，但它占据的空间可能更多；

• 反之一件物品可能价值低，但其所占空间可忽略不计。

而贪心策略只会考虑“眼前的情况”，能够正确得到答案的概率就小了许多。

动态规划与暴力枚举的区别

在暴力枚举的解题过程中，我们不仅仅知道了答案“背包能装的最大价值”，同时还得到了“它是装了哪几件物品”、“装进去的顺序”这些冗余的信息。

而正是这些冗余的信息，影响了我们求解的效率。

但动态规划的特点在于： “我不关心怎么得到答案” ，我只需要知道结果是多少。