背包DP教程：从DFS暴力到DP的逐步推导

· · 算法·理论

前言

:::epigraph[放在前面] 本文源自一位初二年级 OIer 的真实学习笔记与教学反思，愿与你分享从困惑到通透的完整路径。 :::

背包问题是动态规划（DP）最经典的基石。但回想我自己的学习经历，最大的障碍不是问题本身，而是大多数教程都从完美的状态方程 f_{i,j} 开始讲起，甚至有些教程直接从一维数组讲起，加大了学习者的理解难度，造成了学习者的巨大负担。

在本文中，我将介绍背包模型的 DFS、记忆化搜索、二维数组、滚动数组和其他优化，由浅入深。其中，本文最具特色的是拥有 DFS 和记忆化搜索的解释，在洛谷中背包 DP 的极少文章能拥有这两点。

以前，当我还是初学者的时候，就是直接去看一维 DP，导致背包理解不透彻，竟然以为是按照“背包容量”为状态变量。这篇文章的结构，就是复制了我本人的学习经验，那时从困惑到顿悟的学习路线，而不是从教科书上抄来的最优解。
我为什么发表这篇文章？ 就是因为我的很多同学都直接奔着最优解而去，而恰恰忽略了朴素但强大的 DFS，导致理解出问题。所以，我决定写下这篇笔记，从最根源的搜索思维讲起。

01 背包

模型： 给定 N 种物品，第 i 种物品的体积为 w_i，价值为 v_i，每种物品只有 1 件。有一体积为 M 的背包，选择一些物品放入背包，使得在物品总体积不超过 M 的前提下，物品的价值总和最大。

暴力搜索 DFS 方法

很明显，我们面对第 i 件物品，有且只有 2 种选择——选或不选。
当我们理解这个思想的时候，就可以写出代码了。
选是一种情况，不选也是一种情况，分别枚举即可。

整体代码如下（假设 $n,m\leqslant100$）： ```cpp #include <bits/stdc++.h> using namespace std; int n,m; int ans=0; //存储最终结果 int w[105],v[105]; void dfs(int i,int j,int cnt){ //i代表第i个物品，j代表当前背包剩余容量，cnt代表当前已选物品的总价值 if (i>n){ //选完所有物品 ans=max(ans,cnt); //更新最大价值 return; } //选择1：不选第i件物品 //剩余容量不变，当前物品总价值不变 dfs(i+1, j, cnt); //选择2：选择第i件物品（前提是放得下，也就是当前背包容量j大于当前物品重量w[i]） if (j>=w[i]){ //剩余容量减少w[i]，总价值增加v[i]。 dfs(i+1, j-w[i], cnt+v[i]); } } int main() { scanf("%d%d",&n,&m); for (int i=1;i<=n;++i){ scanf("%d%d",&w[i],&v[i]); } //从第1个物品选择，当前剩余容量为m，当前已选物品总价值为0（实际上还没选） dfs(1,m,0); printf("%d",ans); return 0; } ``` 我们发现，物品有 $2$ 种选择**分支**，物品总数为 $n$，因此结点数量为 $2^n$。 如果我们用一个数组 $f$ 记录下第一次计算 $f_{i,j}$ 时得到的从该状态出发能获得的**最大价值**，那么当其他路径再次遇到这个状态时，就可以**直接查表返回**，避免重复的递归展开。这就是**记忆化搜索**。 ## 记忆化搜索方法 在理解了 DFS 的重复计算问题后，一个自然的优化思路是：**将已经计算过的子问题的答案保存起来，避免重复劳动**。这就是记忆化搜索（Memoization）。 我们需要定义一个记忆化数组 $f$，其大小为 $n\times m$。这里 $f_{i,j}$ 的含义与 DFS 中的子问题定义完全一致：**从第 $i$ 个物品开始考虑，剩余容量为 $j$ 时，能获得的最大价值**。 **实现方法**：将 $f$ 数组初始化为 $-1$，并用 $f_{i,j}\ne-1$ 来判断。由于在大部分题目中，物品重量和物品价值都是**正整数**，因此如果用 $-1$ 代表未计算（非法）的情况，可以用于标记。 我们将 $f$ 数组初始化为一个**不可能取到的值 $-1$**，用 `if (f[i][j]==-1)` 来判断该状态是否已被计算过。 优化后的整体代码如下： ```cpp #include <bits/stdc++.h> using namespace std; int n,m,w[1005],v[1005],f[1005][1005]; // f将初始化为-1 int dfs_memo(int i, int j) { if (i>n) return 0; // 关键：f[i][j]!=-1表示已计算。因为任何合法解都是正整数，所以-1是安全的哨兵值。 if (f[i][j] != -1) return f[i][j]; // 不选第i个物品， int res=dfs_memo(i+1, j); // 决策2：选第i个物品（前提是能放下） if (j>=w[i]){ res = max(res, dfs_memo(i+1,j-w[i])+v[i]); } return f[i][j] = res; //存储并返回 } int main() { memset(f, -1, sizeof f); //统一初始化为-1 scanf("%d%d",&n,&m); for (int i=1;i<=n;++i){ scanf("%d%d",&w[i],&v[i]); } printf("%d",dfs_memo(1, m)); return 0; } ``` 朴素 DFS 的低效，根源在于对同一状态 $(i,j)$ 的重复计算。那么，最直接的改进方案就是：为每个状态设立一个**备忘录**。第一次计算出 $(i,j)$ 的结果后，将它存起来；之后再遇到相同的状态，就直接查表返回结果，无需再次展开递归。这种**带备忘录的递归**就是记忆化搜索。 **注意**：记忆化搜索有**栈溢出**风险。系统调用栈的空间有限，当递归深度（与物品数 $n$ 相关）较大时，**极易引发 RE（运行时错误）**。递推式的 DP 正好能避免这样的危险。 > 讲到这里你可能想问：“既然记忆化搜索有缺陷，为什么还要费劲讲它？” > 因为**我的目标是让你理解，而不是仅仅记住**。记忆化搜索的 $f_{i,j}$ 和 DFS 的参数 $(i,j)$ 是**完全对应**的，这个**状态**的定义是从问题里**自然长出来**的，不是凭空变出来的。理解了它，你才能自己设计其他 DP 问题的状态。 > **这就是为什么我从DFS开始**：当你理解了“从第 $i$ 个物品开始考虑，剩余容量为 $j$”这个最自然的子问题定义，你才能真正理解后续所有优化的**为什么**，而不仅仅是**怎么做**。 ## 01 背包问题 DP 方法 ### 阶段划分 很明显，问题规模受 $n,m$ 的限制，我们如何划分阶段呢？ 逐一考虑每件物品是否加入背包，阶段变量 $i$代表前 $i$ 件物品，阶段变量 $j$ 代表当前容量为 $j$。 这样定义的话，$f_{i,j}$ 就代表当选择前 $i$ 件物品，背包容量为 $j$ 的情况下的最优选择。 ### 状态定义 按照这样的阶段划分及**最优子结构**性质，我们可以如下定义： **若不选第 $i$ 个物品，则** $$f_{i,j}=f_{i-1,j}$$ **解释**： 既然不选第 $i$ 个物品，那么前 $i$ 个物品的最优解，自然就等于只考虑前 $i−1$ 个物品、且容量同样为 $j$ 时的最优解。 **若选第 $i$ 个物品，则** $$f_{i,j}=f_{i-1,j-w_i}+v_i\text{，当 }j\geqslant w_i\text{ 时}$$ **解释：** $j-w_i$ 代表在背包容量 $j$ 下，我们可以舍弃掉 $w_i$ 的背包容量，换取 $v_i$ 的价值。 综上，根据**最优子结构**性质，$f_{i,j}$ 的值有上述的大者决定，即 $$ f_{i,j}=\max\begin{cases} f_{i-1,j}\\ f_{i-1,j-w_i}+v_i&j\geqslant w_i \end{cases} $$ ### 代码实现 定义一个 $f$ 数组，大小为 $n\times m$，初始化为 $0$，用来存储当前 $f_{i,j}$ 的状态，$n,m$ 的含义参见 **01 背包模型**，关键代码如下 ```cpp for (int i=1;i<=n;++i){ for (int j=0;j<=m;++j){ f[i][j] = f[i-1][j]; //继承，表示如果不选第i个物品 if (j>=w[i]){ //一定要判断！否则数组越界！！ f[i][j]=max(f[i][j], f[i-1][j-w[i]]+v[i]); //比较最大值 } } } ``` 最终答案存储在 `f[n][m]`，输出即可。 ### 01 背包滚动数组优化 很明显，上述代码时间复杂度为 $O(nm)$，空间复杂度为 $O(nm)$，我们可以使用**滚动数组**进行优化**空间复杂度**。 **观察这个状态转移方程：** $$ f_{i,j}=\max\begin{cases} f_{i-1,j}\\ f_{i-1,j-w_i}+v_i&j\geqslant w_i \end{cases} $$ 我们可以发现，如果要确定第 $i$ 行的数据，仅需知道第 $i-1$ 行的数据，其余数据均为**无用数据**。 因此，我们使用两个数组，一个存第 $i$ 行的数据，另一个存第 $i-1$ 行的数据，大小都是 $m$。 实际上，我们常定义一个二维数组 $f$，大小为 $2\times m$，这样的连续内存可以使缓存命中率提高。 关键代码如下： ```cpp for (int i=1;i<=n;++i){ for (int j=0;j<=m;++j){ int t1=i%2; //当前行 int t2=(i-1)%2; //上一行 //可替换为 t1=i&1,t2=(i-1)&1，性能更佳 f[t1][j] = f[t2][j]; //继承，表示如果不选第i个物品 if (j>=w[i]){ //防止数组越界 f[t1][j]=max(f[t1][j], f[t2][j-w[i]]+v[i]); } } } ``` 由于我们是按照顺序处理的，在处理完第 $n$ 个物品后，最终结果实际存储在 `f[n%2][m]`。 ### 01 背包降维优化 **请确保您已经彻底了解 01 背包基础状态转移方程！！！** 直接给出**降维优化**状态转移方程： $$ f_j=\max\begin{cases} f_j\\ f_{j-w_i}+v_i \end{cases} $$ 关键代码如下： ```cpp for (int i=1;i<=n;++i){ for (int j=m;j>=w[i];--j){ f[j]=max(f[j], f[j-w[i]]+v[i]); } } ``` **解释：** 我们知道，01背包的要求就是每件物品只能选择 $1$ 次。 那么，阶段变量 $j$ 从 $m$ 到 $w_i$（简称**倒序遍历**），可以保证 $f_{j-w_i}+v_i$ 一定在 $f_j$ 之后修改，这样就能保证只选 $1$ 次。 试想一下，如果 $j$ 从 $w_i$ 到 $m$ 遍历（简称**正序遍历**），可能会导致 $f_{j-w_i}+v_i$ 可能在 $f_j$ 之前被修改，导致每件物品可能选多次。 **倒序遍历**能够保证在更新 $f_j$ 时，用到的 $f_{j-w_i}$ 一定是**上一轮**的值，从而使每件物品**只被考虑一次**。 正序遍历和逆序遍历的后果如下： **实例演示**（物品：重量 $2$，价值 $3$；背包容量 $5$）： :::success[逆序遍历过程] - $j=5$：$\max(f_5,f_3+3)=\max(0,0+3)=3

推荐练习题目：

提示：

适用场景：

:::warning[易错点]

真正的突破是当我发现：如果允许重复选，那么状态转移方程中，选第 i 件物品时，依赖的其实是 f_{i,j-w_i} （同一行），而不是 f_{i-1,j-w_i}（上一行）。

这个发现让我震惊：原来 01 背包和完全背包的本质区别，就是这一个下标的差别！这直接导致了代码中 j 的遍历方向相反。

所以，在本文中，我会先带你走我走过的路——从枚举 k 开始，理解问题本质；然后再带你看到更优美的优化——理解为什么只需要改一个下标。 ::: 模型： 给定 n 种物品，其中第 i 种物品的体积为 w_i（w_i\geqslant1），价值为 v_i，每种物品有无数件。有一体积为 m 的背包，请选择一些物品放入背包，使得在物品总体积不超过 m 的前提下，物品的价值总和最大。

暴力搜索 DFS 方法

首先，完全背包与01背包不同的是：01背包每件物品只能选择 1 次，而完全背包可以选择若干次！
如果是01背包，我们直接枚举它选或不选即可，但完全背包呢？
我们可以用一个状态变量 k，表示第 i 件物品选 k 个。
根据实际情况，k 的取值范围应当为 0\leqslant k\leqslant\left\lfloor\dfrac j{w_i}\right\rfloor，表示最少选 0 个，枚举到装不下为止。

整体代码如下：

#include <bits/stdc++.h>
using namespace std;
int n,m;
int ans=0; //存储最终结果
int w[105],v[105];
void dfs(int i,int j,int cnt){
    //i代表第i个物品，j代表当前背包剩余容量，cnt代表当前已选物品的总价值
    if (i>n){ //选完所有物品
        ans=max(ans,cnt); //更新最大价值
        return;
    }

    //选择k个第i件物品，进行枚举（包含不选，也就是k=0的情况下）
    for (int k=0;k*w[i]<=j;++k){
        dfs(i+1,j-k*w[i],cnt+k*v[i]);
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;++i){
        scanf("%d%d",&w[i],&v[i]);
    }
    //从第1个物品选择，当前剩余容量为m，当前已选物品总价值为0（实际上还没选）
    dfs(1,m,0);
    printf("%d",ans);
    return 0;
}

由于完全背包的第 i 件物品的决策实际上有 (k+1) 个。 又因为最坏情况下 k=\left\lfloor\dfrac m{w_i}\right\rfloor，同时 w_i=1，则总时间复杂度为 O((m+1)^n)。

观察完全背包的选择路线，我们可以发现，有很多重复计算的节点，因此，我们可以像01背包一样使用记忆化搜索，用一个 f 数组记录 f_{i,j} 时得到的从该状态出发能获得的最大价值，如果其他路径再次遇到这个状态，可以直接查表返回。

类似地，我们用直接枚举的方法，代码就是这样的：

#include <bits/stdc++.h>
using namespace std;
int n,m;
int ans=0; //存储最终结果
int w[105],v[105];
void dfs(int i,int j,int cnt){
    //i代表第i个物品，j代表当前背包剩余容量，cnt代表当前已选物品的总价值
    if (i>n){ //选完所有物品
        ans=max(ans,cnt); //更新最大价值
        return;
    }
    dfs(i+1,j,cnt); //不选第i件物品
    if (j>=w[i]){
        dfs(i,j-w[i],cnt+v[i]); // 最特别地！！！
        // 这里的i不加1，是因为我们还可以重复选择这件物品
        // cnt+v[i] 表示我们选择了这件物品，增加了它的价值
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;++i){
        scanf("%d%d",&w[i],&v[i]);
    }
    //从第1个物品选择，当前剩余容量为m，当前已选物品总价值为0（实际上还没选）
    dfs(1,m,0);
    printf("%d",ans);
    return 0;
}

记忆化搜索 方法

首先，由于背包受到 i,j,k 三个阶段变量的制约，因此，我们可以很自然地想到：定义一个三维数组 f，大小为 n\times m\times k，实际操作中，f 数组的大小为 n\times m\times m。
但是，由于这样的代码实在过于复杂，而且空间复杂度到了不可承受的地步，只要 n,m 稍微大一点点，就会导致 MLE。

因此，我们可以换一种思路：不使用 k 来标记，用完全背包的最优子结构性质，存储 f_{i,j} 的最优解。

整体代码如下：

#include <bits/stdc++.h>
using namespace std;
int w[105],v[105],f[1005][10005];
int m,n;
int dfs_memo(int i, int j){
    //i表示第i件物品，j表示当前背包剩余容量为j
    if (i>n) return 0; //选完所有物品
    if (f[i][j] != -1) return f[i][j];

    int res = dfs_memo(i+1, j); //不选第i个物品
    for (int k=1;k*w[i]<=j;++k){
        //虽然不用k标记，但实际操作中需要使用k
        int choose = dfs_memo(i+1, j-k*w[i])+k*v[i];
        res = max(res, choose);
    }
    return f[i][j] = res;
}
int main()
{
    memset(f,-1,sizeof f);
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;++i){
        scanf("%d%d",&w[i],&v[i]);
    }
    printf("%d",dfs_memo(1,m));
    return 0;
}

同理，我们也可以用直接枚举的方法来书写代码。
整体代码如下：

#include <bits/stdc++.h>
using namespace std;
int w[105],v[105],f[1005][10005];
int m,n;
int dfs_memo(int i, int j){
    //i表示第i件物品，j表示当前背包剩余容量为j
    if (i>n) return 0; //选完所有物品
    if (f[i][j] != -1) return f[i][j];

    int res = dfs_memo(i+1, j); //不选第i个物品
    if (j>=w[i]){
        res = max(res, dfs_memo(i,j-w[i]) + v[i]);
        //最重要的是i不能+1，否则就会退化为01背包，失去重复选择的特性
        //因为还是i就表示还是选择第i件物品
    }
    return f[i][j] = res;
}
int main()
{
    memset(f,-1,sizeof f);
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;++i){
        scanf("%d%d",&w[i],&v[i]);
    }
    printf("%d",dfs_memo(1,m));
    return 0;
}

同样地，由于 n 的增大，被占用的栈空间不断增多，最终耗尽栈空间，引发 RE。
这个时候就要用递推式的 DP 出场了。

完全背包 DP 方法

阶段划分

问题受 n,m 的限制，同时还要判断要选多少件，设为 k 件，k\geqslant1。
参考01背包和朴素 DFS，我们可以列出如下基础完全背包状态转移方程：

f_{i,j}=\max\begin{cases} f_{i-1,j}\\ f_{i-1,j-w_i\times k}+v_i\times k&j\geqslant w_i\times k \end{cases}

其中，f_{i-1,j-w_i\times k}+v_i\times k 表示在背包容量为 j 的情况下，用去 w_i\times k 的体积，换取 v_i \times k 的价值。
由于放入的物品总体积不能超过 j，又选择 k 个，因此 j\geqslant w_i\times k。

代码实现

关键代码如下：

for (int i=1;i<=n;++i){
    for (int j=0;j<=m;++j){
        f[i][j] = f[i-1][j]; //继承，当k=0，即不选第i件物品的情况
        for (int k=1;k*w[i]<=j;++k){
            f[i][j]=max(f[i][j], f[i-1][j-k*w[i]]+k*v[i]); //比较选多少种好
        }
    }
}

最终结果存储在 f[n][m] 中，输出即可。

当然，在前面提到，我们可以用不断放物品，直到放不下为止，也就是

f_{i,j}=\max\begin{cases} f_{i-1,j}\\ f_{i,j-w_i}+v_i&j\geqslant w_i \end{cases}

这个公式正好对应了上面的 DFS 思路：dfs(i, j-w[i], cnt+v[i]) 中的 i 不变，意味着我们可以继续考虑同一件物品；而 f_{i,j-w_i} 正是依赖同一行（当前物品）的之前状态。

关键代码如下：

for (int i=1;i<=n;++i){
    for (int j=0;j<=m;++j){
        f[i][j] = f[i-1][j]; //继承，当k=0，即不选第i件物品的情况
        if (j>=w[i]){
            f[i][j]=max(f[i][j], f[i][j-w[i]]+v[i]);
        }
    }
}

这样，时间复杂度优化为 O(nm)，大大提高了效率。

完全背包滚动数组优化

我们发现，完全背包的第 i 行同样只依赖第 i-1 行，因此可以进行滚动数组优化。
定义一个数组 f，大小为 2\times m。

关键代码如下：

for (int i=1;i<=n;++i){
    int curr=i%2; //当前行
    int prev=(i-1)%2; //上一行
    for (int j=0;j<=m;++j){ //从0开始，因为j=0时只能不选
        f[curr][j] = f[prev][j];  // 不选当前物品
        if (j>=w[i]){
            f[curr][j]=max(f[curr][j], f[curr][j-w[i]]+v[i]);
            //这里依赖的是f[curr][j-w[i]]，即当前行的值，体现了完全背包可重复选择的特性
        }
    }
}

该代码与01背包不同的就是当 j\geqslant w_i 时，f_{curr,j-w_i}+v_i 体现了重复选择。
同样地，由于我们是按照顺序处理的，所以答案同样存储在 f[n%2][m]。

完全背包降维优化

前面讲过，01背包需要倒序遍历才能使得只选一次，正序遍历会导致多次选择，完全背包正好符合正序遍历的要求，因此完全背包的降维优化是正序遍历的。

f_j=\max\begin{cases} f_j\\ f_{j-w_i}+v_i \end{cases}

关键代码如下：

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

最终结果存储在 f[m] 中，输出即可。

同样地，我们演示正序遍历的结果：
实例演示（物品：重量 2，价值 3；背包容量 5）： :::success[正序遍历过程]

结果：物品被重复选择，最大价值 6=3\times2！ ::: 推荐练习题目：

提示：

与 01 背包的关键区别：

适用场景：

:::warning[易错点]

完整代码如下：

#include <bits/stdc++.h>
using namespace std;
int n,m,w[105],v[105],c[105];
int ans;
//这里的 w,v,c数组均与模型中描述的功能已知
void dfs(int i,int j,int cnt){
    //i代表第i个物品
    //j代表当前背包剩余容量为j
    //cnt代表当前已选择的物品的总价值

    if (i>n){
        ans=max(ans, cnt);
        return;
    }
    //k=0表示不选，其它的就是 k的取值范围
    for (int k=0;k<=min(c[i],j/w[i]);++k){
        dfs(i+1,j-k*w[i],cnt+k*v[i]);
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;++i){
        scanf("%d%d%d",&w[i],&v[i],&c[i]);
    }
    dfs(1,m,0);
    printf("%d",ans);
    return 0;
}

由于多重背包的每件物品的决策有 k 个，参考完全背包的朴素 DFS，其中 k=\left\lfloor\dfrac m{w_i}\right\rfloor+1。因此时间复杂度为

O\left(\left(\left\lfloor\dfrac m{w_i}\right\rfloor+1\right)^n\right)

记忆化搜索 方法

根据多重背包背包的最优子结构性质，我们可以使用一个 f 数组记录 f_{i,j} 时得到的从该状态出发能获得的最大价值，也就是记忆化搜索。 完整代码如下：

#include <bits/stdc++.h>
using namespace std;
int n,m,w[105],v[105],c[105];
int f[105][40005];
int dfs_memo(int i,int j){
    //i表示第i件物品，j表示当前背包剩余容量为j
    if (i>n) return 0; //选完所有物品
    if (f[i][j]!=-1) return f[i][j];

    int res=dfs_memo(i+1,j); //不选第i件物品
    for (int k=1;k<=min(c[i],j/w[i]);++k){
        //选择物品
        int choose = dfs_memo(i+1, j-k*w[i])+k*v[i];
        res=max(res, choose);
    }
    return f[i][j] = res;
}
int main()
{
    memset(f,-1,sizeof f);
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;++i){
        scanf("%d%d%d",&v[i],&w[i],&c[i]);
    }
    printf("%d",dfs_memo(1,m));
    return 0;
}

多重背包 DP 方法

阶段划分

问题受 n,m 的限制，同时还要考虑每件物品的数量限制 c_i。
参考完全背包，我们可以列出如下基础多重背包状态转移方程：

f_{i,j}=\max\begin{cases} f_{i-1,j}\\ f_{i-1,j-w_i\times k}+v_i\times k&k\leqslant\min\left(c_i,\left\lfloor\dfrac j{w_i}\right\rfloor\right) \end{cases}

其中，k 表示选择当前物品的数量，不能超过物品的总数量 c_i，也不能超过背包容量限制 \left\lfloor\dfrac j{w_i}\right\rfloor。

代码实现

关键代码如下：

for (int i=1;i<=n;++i){
    for (int j=0;j<=m;++j){
        f[i][j] = f[i-1][j]; //继承，不选当前物品
        for (int k=1;k<=min(c[i],j/w[i]);++k){
            f[i][j]=max(f[i][j], f[i-1][j-k*w[i]]+k*v[i]);
        }
    }
}

最终结果存储在 f[n][m] 中，输出即可。 :::success[基础解法过程] 实例演示（物品：重量 2，价值 3，数量 2；背包容量 5）：

关键代码：

for (int i=1;i<=n;++i){
    int curr=i%2; //当前行（第i行）
    int prev=(i-1)%2; //上一行（第i-1行）
    for (int j=0;j<=m;++j){
        f[curr][j] = f[prev][j];  // 不选当前物品
        for (int k=1;k<=min(c[i],j/w[i]);++k){
            f[curr][j]=max(f[curr][j], f[prev][j-k*w[i]]+k*v[i]);
        }
        //也可以让 k从 0到 min(c[i],j)，这样就有不选的意思，但是我这样写可以更清晰
        //两种写法性能差异不大
    }
}

同样地，由于我们是按照顺序处理的，最终结果存放在 f[n%2][m]，输出即可。

多重背包二进制优化

由于多重背包三重循环的时间复杂度是 O\left(nm\cdot\min\left(c_i,~\dfrac m{w_i}\right)\right)，在 c_i 较大时效率很低。

二进制优化原理：
任何一个正整数都可以表示为若干个 2 的幂次之和。
通过二进制拆分，我们将数量为 c_i 的物品拆分成 \log_2c_i 个“新物品”，每个新物品的数量是 2 的幂次，从而将多重背包转化为 01 背包问题。

二进制拆分示例：
假设某物品有 13 个，我们拆分为 13=1+2+4+6（因为 1+2+4=7<13，剩余 6）
这样用 1,2,4,6 这四个"新物品"就能组合出 0\sim13 的所有数量！

为什么我们可以这样拆分？
因为 1、2、4 可以组合出 0\sim7 的所有数，加上 6 后就能覆盖 0\sim13 的全部范围。

二进制优化完整实现：

#include <bits/stdc++.h>
using namespace std;
int n,m;// 原始数据
vector<int> new_w,new_v; // 存储拆分后的物品
// 这里用vector，是因为我们不需要知道二进制拆分后的数据长度是多少
int main()
{
    scanf("%d%d",&n,&m);
    // 二进制拆分
    for (int i=0;i<n;++i){
        int w,v,c;
        scanf("%d%d%d",&w,&v,&c);

        // 二进制拆分
        for (int k=1;k<=c;k*=2){
            if (k*w>m) break; // 拆分出的单件物品已超总容量，无法放入，停止拆分
            new_w.push_back(w*k);
            new_v.push_back(v*k);
            c-=k;
        }
        if (c>0){
            new_w.push_back(w*c);
            new_v.push_back(v*c);
        }
    }

    // 转换为01背包
    vector<int>f(m+5,0);
    int new_n=new_w.size();

    //按照01背包的步骤来做，只是替换为新的物品数量、价值和重量
    for (int i=0;i<new_n;++i){
        for (int j=m;j>=new_w[i];--j){
            f[j]=max(f[j],f[j-new_w[i]]+new_v[i]);
        }
    }
    printf("%d",f[m]);
    return 0;
}

时间复杂度优化为 O(nm\cdot\sum\log c_i)，大大提高了效率。

当然，在二进制拆分后，你也可以按照 01 背包的二维数组、滚动数组进行计算。此处不再展开。

多重背包总结

实现方法 时间复杂度 空间复杂度 缓存友好度 代码复杂度
朴素 DFS O\left(\left(\left\lfloor\dfrac m{w_i}\right\rfloor+1\right)^n\right) O(n) 差 极简
记忆化搜索 O\left(nm\cdot\min\left(c_i,~\left\lfloor\dfrac m{w_i}\right\rfloor\right)\right) O(nm) 差 差 较复杂
二维数组 O\left(nm\cdot\min\left(c_i,~\left\lfloor\dfrac m{w_i}\right\rfloor\right)\right) O(nm) 一般 简单
滚动数组 O\left(nm\cdot\min\left(c_i,~\left\lfloor\dfrac m{w_i}\right\rfloor\right)\right) O(m) 较高 较高 中等
二进制优化 O(m\cdot\sum\log c_i) O(m) 高 复杂

提示：

与其他背包的关系：

推荐练习题目：

适用场景建议：

::::warning[易错点]

其中，DFS 能够帮助初学者理解背包问题的本质，从而更好地学习背包优化、背包变种问题。

致谢与创作谈：

Q：看完文章我还是不懂，是不是我太笨了？
A：绝对不是！ 我当初学背包时，每个阶段都卡过：

我的建议：不要试图一次全懂。你可以这样：

给自己至少两周的时间让这些概念在脑子里沉淀。动态规划是需要反刍的知识。

Q：为什么提交 DFS 或记忆化搜索代码会出现 RE？
A：这通常是由于递归深度过大导致栈溢出。系统递归栈的深度有限，当物品数 n 很大时，递归层数可能超出限制。这正是一个生动的教训：我们学习 DFS 和记忆化是为了理解思想，但在竞赛实战中，必须将其转化为更稳定、高效的迭代 DP 代码。

Q：多重背包的二进制优化为什么有效？
A：其有效性基于一个数学事实：任何正整数都可以由若干个 2 的幂次和一个剩余数组合表示。通过这种拆分，我们将选择 0\sim c 个物品的 O(c) 次决策，转化为对 O(\log_2c) 个新物品的 01 背包问题。这本质上是一种信息压缩，用更少的状态表达了全部的可能性。

Q：背包问题中最容易忽略的关键点是什么？
A：初始化和状态定义的语义。这直接对应了问题的两种不同要求（以二维数组为例）：

您需遵守下列条件：

最后，欢迎各位读者引用本文（需注明文章来源和署名），祝您背包 DP 之路一帆风顺！