专栏文章

零基础背包DP指南

ZZhangChuan1350
算法·理论参与者 4已保存评论 4

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
4 条
当前快照
1 份
快照标识符
@mkik1rvv
此快照首次捕获于
2026/01/18 01:02
上个月
此快照最后确认于
2026/01/18 01:02
上个月
查看原文

前言

本文源自一位八年级 OIer 的真实学习笔记与教学反思，愿与你分享从困惑到通透的完整路径。
放在前面
背包问题是动态规划（DP）最经典的基石。但回想我自己的学习经历，最大的障碍不是问题本身，而是大多数教程都从完美的状态方程 fi,jf_{i,j} 开始讲起，甚至有些教程直接从一维数组讲起，加大了学习者的理解难度，造成了学习者的巨大负担。
在本文中，我将介绍背包模型的 DFS、记忆化搜索、二维数组、滚动数组和其他优化，由浅入深。其中，本文最具特色的是拥有 DFS 和记忆化搜索的解释，在洛谷中背包 DP 的极少文章能拥有这两点。
以前，当我还是初学者的时候，就是直接去看一维 DP，导致背包理解不透彻，竟然以为是按照“背包容量”为状态变量。这篇文章的结构，就是复制了我本人的学习经验，那时从困惑到顿悟的学习路线，而不是从教科书上抄来的最优解。
我为什么发表这篇文章？ 就是因为我的很多同学，它们直接奔着最优解而去，而恰恰忽略了朴素但强大的 DFS，导致理解出问题。我不希望再重演。

01 背包

模型： 给定 NN 种物品，第 ii 种物品的体积为 wiw_i，价值为 viv_i，每种物品只有 11 件。有一体积为 MM 的背包，选择一些物品放入背包，使得在物品总体积不超过 MM 的前提下，物品的价值总和最大。

暴力搜索 DFS 方法

很明显，我们面对第 ii 件物品，有且只有 22 种选择——选或不选。
当我们理解这个思想的时候，就可以写出代码了。
选是一种情况，不选也是一种情况，分别枚举即可。
nn 代表物品数量，mm 代表背包容量，数组 w,vw,v 分别存储物品重量和价值、
整体代码如下（假设 n,m⩽100n,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;
}
我们发现，物品有 22 种选择分支，物品总数为 nn，因此结点数量为 2n2^n。
如果我们用一个数组 ff 记录下第一次计算 fi,jf_{i,j} 时得到的从该状态出发能获得的最大价值，那么当其他路径再次遇到这个状态时，就可以直接查表返回，避免重复的递归展开。这就是记忆化搜索。

记忆化搜索方法

在理解了 DFS 的重复计算问题后，一个自然的优化思路是：将已经计算过的子问题的答案保存起来，避免重复劳动。这就是记忆化搜索（Memoization）。
我们需要定义一个记忆化数组 ff，其大小为 n×mn\times m。这里 fi,jf_{i,j} 的含义与 DFS 中的子问题定义完全一致：从第 ii 个物品开始考虑，剩余容量为 jj 时，能获得的最大价值。
实现方法：将 ff 数组初始化为 −1-1，并用 fi,j≠−1f_{i,j}\ne-1 来判断。由于在大部分题目中，物品重量和物品价值都是正整数，因此如果用 −1-1 代表未计算（非法）的情况，可以用于标记。
我们将 ff 数组初始化为一个不可能取到的值 −1-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) 的重复计算。那么，最直接的改进方案就是：为每个状态设立一个备忘录。第一次计算出 (i,j)(i,j) 的结果后，将它存起来；之后再遇到相同的状态，就直接查表返回结果，无需再次展开递归。这种带备忘录的递归就是记忆化搜索。
注意：记忆化搜索有栈溢出风险。系统调用栈的空间有限，当递归深度（与物品数 nn 相关）较大时，极易引发 RE（运行时错误）。递推式的 DP 正好能避免这样的危险。
讲到这里你可能想问：“既然记忆化搜索有缺陷，为什么还要费劲讲它？”
因为我的目标是让你理解，而不是仅仅记住。记忆化搜索的 fi,jf_{i,j} 和 DFS 的参数 (i,j)(i,j) 是完全对应的，这个状态的定义是从问题里自然长出来的，不是凭空变出来的。理解了它，你才能自己设计其他 DP 问题的状态。
这就是为什么我从DFS开始：当你理解了“从第 ii 个物品开始考虑，剩余容量为 jj”这个最自然的子问题定义，你才能真正理解后续所有优化的为什么，而不仅仅是怎么做。

01 背包问题 DP 方法

阶段划分

很明显，问题规模受 n,mn,m 的限制，我们如何划分阶段呢？
逐一考虑每件物品是否加入背包，阶段变量 ii代表前 ii 件物品，阶段变量 jj 代表当前容量为 jj。
这样定义的话，fi,jf_{i,j} 就代表当选择前 ii 件物品，背包容量为 jj 的情况下的最优选择。

状态定义

按照这样的阶段划分及最优子结构性质，我们可以如下定义：
若不选第 ii 个物品，则 fi,j=fi−1,jf_{i,j}=f_{i-1,j}
解释： 既然不选第 ii 个物品，那么前 ii 个物品的最优解，自然就等于只考虑前 i−1i−1 个物品、且容量同样为 jj 时的最优解。
若选第 ii 个物品，则 fi,j=fi−1,j−wi+vi，当 j⩾wi 时f_{i,j}=f_{i-1,j-w_i}+v_i\text{，当 }j\geqslant w_i\text{ 时} 解释： j−wij-w_i 代表在背包容量 jj 下，我们可以舍弃掉 wiw_i 的背包容量，换取 viv_i 的价值。
综上，根据最优子结构性质，fi,jf_{i,j} 的值有上述的大者决定，即
fi,j=max⁡{fi−1,jfi−1,j−wi+vij⩾wif_{i,j}=\max\begin{cases} f_{i-1,j}\\ f_{i-1,j-w_i}+v_i&j\geqslant w_i \end{cases}

代码实现

定义一个 ff 数组，大小为 n×mn\times m，初始化为 00，用来存储当前 fi,jf_{i,j} 的状态，n,mn,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)，空间复杂度为 O(nm)O(nm)，我们可以使用滚动数组进行优化空间复杂度。
观察这个状态转移方程：
fi,j=max⁡{fi−1,jfi−1,j−wi+vij⩾wif_{i,j}=\max\begin{cases} f_{i-1,j}\\ f_{i-1,j-w_i}+v_i&j\geqslant w_i \end{cases}
我们可以发现，如果要确定第 ii 行的数据，仅需知道第 i−1i-1 行的数据，其余数据均为无用数据。
因此，我们使用两个数组，一个存第 ii 行的数据，另一个存第 i−1i-1 行的数据，大小都是 mm。
实际上，我们常定义一个二维数组 ff，大小为 2×m2\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]);
        }
    }
}
由于我们是按照顺序处理的，在处理完第 nn 个物品后，最终结果实际存储在 f[n%2][m]。

01 背包降维优化

请确保您已经彻底了解 01 背包基础状态转移方程！！！
直接给出降维优化状态转移方程：
fj=max⁡{fjfj−wi+vif_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背包的要求就是每件物品只能选择 11 次。
那么，阶段变量 jj 从 mm 到 wiw_i（简称倒序遍历），可以保证 fj−wi+vif_{j-w_i}+v_i 一定在 fjf_j 之后修改，这样就能保证只选 11 次。
试想一下，如果 jj 从 wiw_i 到 mm 遍历（简称正序遍历），可能会导致 fj−wi+vif_{j-w_i}+v_i 可能在 fjf_j 之前被修改，导致每件物品可能选多次。
倒序遍历能够保证在更新 fjf_j 时，用到的 fj−wif_{j-w_i} 一定是上一轮的值，从而使每件物品只被考虑一次。
正序遍历和逆序遍历的后果如下：
实例演示（物品：重量 22，价值 33；背包容量 55）：
逆序遍历过程
  • j=5j=5：max⁡(f5,f3+3)=max⁡(0,0+3)=3\max(f_5,f_3+3)=\max(0,0+3)=3
  • j=4j=4：max⁡(f4,f2+3)=max⁡(0,0+3)=3\max(f_4,f_2+3)=\max(0,0+3)=3
  • j=3j=3：max⁡(f3,f1+3)=max⁡(0,0+3)=3\max(f_3,f_1+3)=\max(0,0+3)=3
  • j=2j=2：max⁡(f2,f0+3)=max⁡(0,0+3)=3\max(f_2,f_0+3)=\max(0,0+3)=3
结果：每个物品只选了一次！
误用正序的后果
  • j=2j=2：max⁡(0,f0+3)=3\max(0,f_0+3)=3
  • j=3j=3：max⁡(0,f1+3)=3\max(0,f_1+3)=3
  • j=4j=4：max⁡(0,f2+3)=6=3×2\max(0,f_2+3)=6=3\times2    ←~~~\leftarrow 错误！选了两次！
注意：我们不是只以背包容量作为阶段变量！只是降维！
推荐练习题目：

01背包总结

实现方法时间复杂度空间复杂度缓存友好度代码复杂度
朴素 DFSO(2n)O(2^n)O(n)O(n)差极简
记忆化搜索O(nm)O(nm)O(nm)+O(n)O(nm)+O(n)差较复杂
二维数组O(nm)O(nm)O(nm)O(nm)一般简单
滚动数组O(nm)O(nm)O(2m)O(2m)较高中等
降维优化O(nm)O(nm)O(m)O(m)高简单
提示：
  • 记忆化搜索由于递归深度，空间复杂度在 O(nm)O(nm) 的基础上加 O(n)O(n)。
  • 记忆化搜索由于递归原因，时间复杂度的常数因子比二维数组要大。
适用场景：
  • 理解阶段：DFS 和记忆化搜索必须掌握。
  • 学习阶段：推荐二维数组，易于理解。
  • 竞赛小数据：滚动数组，平衡性能和可读性。
  • 竞赛大数据：一维降维，极致性能。
易错点
  • 记忆化搜索或朴素 DFS 由于 nn 过大，导致栈溢出，引发 RE。
  • 二维数组和滚动数组第 ii 行没有继承第 i−1i-1 行导致错误。
  • 滚动数组误用位运算导致结果错误。
  • 降维优化正序遍历 jj 导致错误（应倒序遍历）。
  • 降维优化本质上是在一行内操作，仅省略了阶段变量 ii，因此需要完全理解二维数组的状态转移再进行学习降维优化。

完全背包

如何理解完全背包
我第一次学完全背包时，和你想的一模一样：用一个循环 for (int k=0;k*w[i]<=j;k++) 来枚举选几件。这是最直观、最符合暴力搜索思维的方法。
但是后来我发现：这种“枚举 kk”的思路写出来的代码是三重循环，效率太低。
真正的突破是当我发现：如果允许重复选，那么状态转移方程中，选第 ii 件物品时，依赖的其实是 fi,j−wif_{i,j-w_i} （同一行），而不是 fi−1,j−wif_{i-1,j-w_i}（上一行）。
这个发现让我震惊：原来 01 背包和完全背包的本质区别，就是这一个下标的差别！这直接导致了代码中 jj 的遍历方向相反。
所以，在本文中，我会先带你走我走过的路——从枚举 kk 开始，理解问题本质；然后再带你看到更优美的优化——理解为什么只需要改一个下标。
模型： 给定 nn 种物品，其中第 ii 种物品的体积为 wiw_i（wi⩾1w_i\geqslant1），价值为 viv_i，每种物品有无数件。有一体积为 mm 的背包，请选择一些物品放入背包，使得在物品总体积不超过 mm 的前提下，物品的价值总和最大。

暴力搜索 DFS 方法

首先，完全背包与01背包不同的是：01背包每件物品只能选择 11 次，而完全背包可以选择若干次！
如果是01背包，我们直接枚举它选或不选即可，但完全背包呢？
我们可以用一个状态变量 kk，表示第 ii 件物品选 kk 个。
根据实际情况，kk 的取值范围应当为 0⩽k⩽⌊jwi⌋0\leqslant k\leqslant\left\lfloor\dfrac j{w_i}\right\rfloor，表示最少选 00 个，枚举到装不下为止。
整体代码如下：
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;
    }

    //选择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;
}
由于完全背包的第 ii 件物品的决策实际上有 (k+1)(k+1) 个。 又因为最坏情况下 k=⌊mwi⌋k=\left\lfloor\dfrac m{w_i}\right\rfloor，同时 wi=1w_i=1，则总时间复杂度为 O((m+1)n)O((m+1)^n)。
观察完全背包的选择路线，我们可以发现，有很多重复计算的节点，因此，我们可以像01背包一样使用记忆化搜索，用一个 ff 数组记录 fi,jf_{i,j} 时得到的从该状态出发能获得的最大价值，如果其他路径再次遇到这个状态，可以直接查表返回。
类似地，我们用“直接枚举”的方法，代码就是这样的：
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;
    }
    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,ki,j,k 三个阶段变量的制约，因此，我们可以很自然地想到：定义一个三维数组 ff，大小为 n×m×kn\times m\times k，实际操作中，ff 数组的大小为 n×m×mn\times m\times m。
但是，由于这样的代码实在过于复杂，而且空间复杂度到了不可承受的地步，只要 n,mn,m 稍微大一点点，就会导致 MLE。
因此，我们可以换一种思路：不使用 kk 来标记，用完全背包的最优子结构性质，存储 fi,jf_{i,j} 的最优解。
整体代码如下：
CPP
#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;
}
同样地，由于 nn 的增大，被占用的栈空间不断增多，最终耗尽栈空间，引发 RE。
这个时候就要用递推式的 DP 出场了。

完全背包 DP 方法

阶段划分

问题受 n,mn,m 的限制，同时还要判断要选多少件，设为 kk 件，k⩾1k\geqslant1。
参考01背包和朴素 DFS，我们可以列出如下基础完全背包状态转移方程：
fi,j=max⁡{fi−1,jfi−1,j−wi×k+vi×kj⩾wi×kf_{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}
其中，fi−1,j−wi×k+vi×kf_{i-1,j-w_i\times k}+v_i\times k 表示在背包容量为 jj 的情况下，用去 wi×kw_i\times k 的体积，换取 vi×kv_i \times k 的价值。
由于放入的物品总体积不能超过 jj，又选择 kk 个，因此 j⩾wi×kj\geqslant w_i\times k。

代码实现

关键代码如下：
CPP
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] 中，输出即可。
当然，在前面提到，我们可以用“不断放物品，直到放不下为止”，也就是
fi,j=max⁡{fi−1,jfi,j−wi+vij⩾wif_{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]) 中的 ii 不变，意味着我们可以继续考虑同一件物品；而 fi,j−wif_{i,j-w_i} 正是依赖同一行（当前物品）的之前状态。
关键代码如下：
CPP
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)O(nm)，大大提高了效率。

完全背包滚动数组优化

我们发现，完全背包的第 ii 行同样只依赖第 i−1i-1 行，因此可以进行滚动数组优化。
定义一个数组 ff，大小为 2×m2\times m。
关键代码如下：
CPP
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⩾wij\geqslant w_i 时，fcurr,j−wi+vif_{curr,j-w_i}+v_i 体现了重复选择。
同样地，由于我们是按照顺序处理的，所以答案同样存储在 f[n%2][m]。

完全背包降维优化

前面讲过，01背包需要倒序遍历才能使得只选一次，正序遍历会导致多次选择，完全背包正好符合正序遍历的要求，因此完全背包的降维优化是正序遍历的。
fj=max⁡{fjfj−wi+vif_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=w[i];j<=m;++j){
        f[j]=max(f[j],f[j-w[i]]+v[i]);
    }
}
最终结果存储在 f[m] 中，输出即可。
同样地，我们演示正序遍历的结果：
实例演示（物品：重量 22，价值 33；背包容量 55）：
正序遍历过程
  • j=2j=2：max⁡(f2,f0+3)=max⁡(0,0+3)=3\max(f_2,f_0+3)=\max(0,0+3)=3。
  • j=3j=3：max⁡(f3,f1+3)=max⁡(0,0+3)=3\max(f_3,f_1+3)=\max(0,0+3)=3。
  • j=4j=4：max⁡(f4,f2+3)=max⁡(0,3+3)=6\max(f_4,f_2+3)=\max(0,3+3)=6。
  • j=5j=5：max⁡(f5,f3+3)=max⁡(0,3+3)=6\max(f_5,f_3+3)=\max(0,3+3)=6。
结果：物品被重复选择，最大价值 6=3×26=3\times2！
推荐练习题目：

完全背包总结

实现方法时间复杂度空间复杂度缓存友好度代码复杂度
朴素 DFSO(m+1)nO(m+1)^nO(n)O(n)差极简
记忆化搜索O(nm⋅⌊mwi⌋)O\left(nm\cdot\left\lfloor\dfrac m{w_i}\right\rfloor\right)O(nm)+O(n)O(nm)+O(n)差较复杂
二维数组 11O(nm⋅⌊mwi⌋)O\left(nm\cdot\left\lfloor\dfrac m{w_i}\right\rfloor\right)O(nm)O(nm)一般简单
二维数组 22O(nm)O(nm)O(nm)O(nm)一般简单
滚动数组O(nm)O(nm)O(2m)O(2m)较高中等
降维优化O(nm)O(nm)O(m)O(m)高简单
提示：
  • 记忆化搜索由于递归深度，空间复杂度在 O(nm)O(nm) 的基础上加 O(n)O(n)。
  • 记忆化搜索由于递归原因，时间复杂度的常数因子比二维数组要大。
  • 如果二维数组采用第 22 个方案，则时间复杂度为 O(nm)O(nm)。
与 01 背包的关键区别：
  • 01 背包：逆序遍历，保证只选一次。
  • 完全背包：正序遍历，允许重复选择。
  • 状态转移：01背包依赖上一行，完全背包可依赖当前行。
  • 核心差异在于状态转移时所依赖的上一状态是来自上一行（01背包）还是本行（完全背包），这直接决定了代码中 jj 的遍历方向。
适用场景：
  • 理解阶段：DFS 和记忆化搜索必须掌握。
  • 学习阶段：推荐二维数组，易于理解。
  • 竞赛小数据：滚动数组，平衡性能和可读性。
  • 竞赛大数据：一维降维，极致性能。
易错点
  • 记忆化搜索或朴素 DFS 由于 nn 过大，导致栈溢出，引发 RE。
  • 二维数组和滚动数组第 ii 行没有继承第 i−1i-1 行导致错误。
  • 二维数组第 22 种方法的状态转移错误（应从 fi,j−wif_{i,j-w_i} 而不是 fi−1,j−wif_{i-1,j-w_i} 转移到 fi,jf_{i,j}）。
  • 滚动数组误用位运算导致结果错误。
  • 降维优化倒序遍历 jj 导致错误（应正序遍历）。
  • 降维优化本质上是在一行内完成操作，只是省略了阶段变量 ii，因此需要深刻理解二维数组的状态转移方程再进行学习降维优化。

多重背包

模型： 给定 nn 种物品，其中第 ii 种物品的体积为 wiw_i，价值为 viv_i，每种物品有 cic_i 件。有一体积为 mm 的背包，请选择一些物品放入背包，使得在物品总体积不超过 mm 的前提下，物品的价值总和最大。

暴力搜索 DFS 方法

我们看到完全背包的朴素 DFS 中，0⩽k⩽⌊jwi⌋0\leqslant k\leqslant\left\lfloor\dfrac j{w_i}\right\rfloor，这是由于完全背包可以无限选择所导致。
然而，多重背包还有物品数量的限制 cic_i，这就要求 k≯cik\ngtr c_i。
综上，在多重背包里，kk 的取值范围为 0⩽k⩽min⁡(ci, ⌊jwi⌋)0\leqslant k\leqslant\min\left(c_i,~\left\lfloor\dfrac j{w_i}\right\rfloor\right)。这样保证每件物品选择数量不超过物品数量 cic_i 和背包容量 ⌊jwi⌋\left\lfloor\dfrac j{w_i}\right\rfloor。
完整代码如下：
CPP
#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;
}
由于多重背包的每件物品的决策有 kk 个，参考完全背包的朴素 DFS，最坏情况下 k=m+1k=m+1。因此最坏时间复杂度为 O((m+1)n)O((m+1)^n)。
根据多重背包背包的最优子结构性质，我们可以使用一个 ff 数组记录 fi,jf_{i,j} 时得到的从该状态出发能获得的最大价值，也就是记忆化搜索。

记忆化搜索 方法

完整代码如下：
CPP
#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,mn,m 的限制，同时还要考虑每件物品的数量限制 cic_i。
参考完全背包，我们可以列出如下基础多重背包状态转移方程：
fi,j=max⁡{fi−1,jfi−1,j−wi×k+vi×kk⩽min⁡(ci,⌊jwi⌋)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}
其中，kk 表示选择当前物品的数量，不能超过物品的总数量 cic_i，也不能超过背包容量限制 ⌊jwi⌋\left\lfloor\dfrac j{w_i}\right\rfloor。

代码实现

关键代码如下：
CPP
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] 中，输出即可。
基础解法过程
实例演示（物品：重量 22，价值 33，数量 22；背包容量 55）：
  • 可选数量范围：min⁡(2,⌊52⌋)=2\min\left(2, \left\lfloor\dfrac 52\right\rfloor\right)=2
  • 比较三种情况：
    • 不选：fi,5=fi−1,5f_{i,5}=f_{i-1,5}
    • 选 11 个：fi−1,3+3f_{i-1,3}+3
    • 选 22 个：fi−1,1+6f_{i-1,1}+6
  • 取最大值作为最终结果

多重背包滚动数组优化

与 01 背包、完全背包类似，多重背包也可以使用滚动数组优化空间。
关键代码：
CPP
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(nm⋅min⁡(ci, mwi))O\left(nm\cdot\min\left(c_i,~\dfrac m{w_i}\right)\right)，在 cic_i 较大时效率很低。
二进制优化原理：
任何一个正整数都可以表示为若干个 22 的幂次之和。
通过二进制拆分，我们将数量为 cic_i 的物品拆分成 log⁡2ci\log_2c_i 个“新物品”，每个新物品的数量是 22 的幂次，从而将多重背包转化为 01 背包问题。
二进制拆分示例：
假设某物品有 1313 个，我们拆分为 13=1+2+4+613=1+2+4+6（因为 1+2+4=7<131+2+4=7<13，剩余 66）
这样用 1,2,4,61,2,4,6 这四个"新物品"就能组合出 0∼130\sim13 的所有数量！
为什么我们可以这样拆分？
因为 1、2、41、2、4 可以组合出 0∼70\sim7 的所有数，加上 66 后就能覆盖 0∼130\sim13 的全部范围。
二进制优化完整实现：
CPP
#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⋅log⁡ci)O(nm\cdot\log c_i)，大大提高了效率。
当然，在二进制拆分后，你也可以按照 01 背包的二维数组、滚动数组进行计算。此处不再展开。

多重背包总结

实现方法时间复杂度空间复杂度缓存友好度代码复杂度
朴素 DFSO((m+1))nO((m+1))^nO(n)O(n)差极简
记忆化搜索O(nm⋅min⁡(ci, ⌊mwi⌋))O\left(nm\cdot\min\left(c_i,~\left\lfloor\dfrac m{w_i}\right\rfloor\right)\right)O(nm)+O(n)O(nm)+O(n)差差
二维数组O(nm⋅min⁡(ci, ⌊mwi⌋))O\left(nm\cdot\min\left(c_i,~\left\lfloor\dfrac m{w_i}\right\rfloor\right)\right)O(nm)O(nm)一般简单
滚动数组O(nm⋅min⁡(ci, ⌊mwi⌋))O\left(nm\cdot\min\left(c_i,~\left\lfloor\dfrac m{w_i}\right\rfloor\right)\right)O(2m)O(2m)较高较高
二进制优化O(m⋅∑log⁡ci)O(m\cdot\sum\log c_i)O(m)O(m)高复杂
提示：
  • 二进制优化的时间复杂度中的 ∑log⁡ci\sum\log c_i 表示拆分后的物品总数。
与其他背包的关系：
  • 当所有 ci=1c_i=1 时：退化为 01 背包。
  • 当所有 ci⩾⌊mwi⌋c_i\geqslant\left\lfloor\dfrac m{w_i}\right\rfloor 时：退化为完全背包。
  • 二进制优化后：转化为01 背包问题。
推荐练习题目：
适用场景建议：
  • 理解阶段：DFS 和记忆化搜索必须掌握。
  • 学习阶段：基础解法，理解多重背包本质。
  • 竞赛实战：二进制优化，平衡效率与实现难度。
易错点
  • 记忆化搜索或朴素 DFS 未判断 k⩽cik\leqslant c_i 的情况，导致退化为完全背包。
  • 记忆化搜索或朴素 DFS 由于 nn 过大，导致栈溢出，引发 RE。
  • 二维数组和滚动数组第 ii 行没有继承第 i−1i-1 行导致错误。
  • 滚动数组误用位运算导致结果错误。
  • 二进制拆分后，问题已转化为对若干独立新物品的01背包问题，因此内层循环必须使用倒序枚举 jj，这与01背包的要求完全一致。
  • 复杂的单调队列导致编写错误。

结语

本文介绍了01 背包、完全背包、多重背包的 DFS 暴力搜索到动态规划，由浅入深，非常适合刚刚入门背包问题的新手学习。
其中，DFS 能够帮助初学者理解背包问题的本质，从而更好地学习背包优化、背包变种问题。
致谢与创作谈：
  • 感谢各位 OIer 的阅读。为求表达更流畅，本文使用了 DeepSeek 进行语句润色，但全文的知识脉络、代码实践、教学设计，皆出自我个人的学习沉淀。
  • 我是怎么写这篇文章的？ 我没有打草稿的习惯，习惯在脑子里把一个问题彻底想穿，同时边写边想：从 DFS 的递归树长啥样，到 fi,jf_{i,j} 这个状态到底在指什么，再到为什么 jj 要倒着遍历——全都想明白了，才打开编辑器一气呵成，写完后进行改动。
    在最开始的时候，这篇文章只有 DP 的内容；后来，我加上 DFS 和记忆化搜索，变得更符合初学者的学习路线，同时加上优秀作品，从 1000010000 字到了 2400024000 字。还加上了版权
    因此，你看到的文章结构，就是我去年啃背包时大脑中的思考流程图。文中的每个“易错点”，都是我提交记录里真实的 WA 与 RE 换来的教训。
  • 特别感谢《信息学奥林匹克竞赛实战笔记 B 册》（浙江大学出版社）这部指导书，作者在学习 DP 的时候就用到这本书，收获颇多。
  • 由于作者水平有限及时间仓促，文中如有疏漏之处，欢迎批评指正和评论该文章。
  • 作者一般节假日和工作日晚上 99 点以后在线，会尽快处理各位读者的评论，若您的评论长时间未得到处理，请耐心等待。
  • 希望您能够在这篇文章了解背包、学习背包、深悟背包。
    • 如果你是蒟蒻，你可以从这篇文章学习到完整的学习路径的背包 DP。
    • 如果你是神犇，你可以通过这篇文章来回顾自己的背包 DP。

洛谷其他背包 DP 优秀文章

站外背包 DP 优秀作品

常见问题解答

Q：为什么我复制你的代码后输出不正确？
A：因为有些题目输入的顺序不同，以洛谷 P1048 采药为例，我的代码是先输入 nn（物品总数），再输入 mm（背包容量），但是很明显，这道题是反过来的。
我的建议：要深刻理解背包的思想，自己“手搓”出来的代码才是最真实的，最符合实际题目的。
Q：看完文章我还是不懂，是不是我太笨了？
A：绝对不是！ 我当初学背包时，每个阶段都卡过：
  • DFS 觉得这有什么用
  • 记忆化搜索觉得好麻烦
  • 二维 DP 觉得公式好复杂
  • 降维优化觉得为什么 jj 要倒着遍历。
我的建议：不要试图一次全懂。你可以这样：
  • 今天看懂 DFS，写几道题
  • 明天再看记忆化搜索
  • 再过几天看二维 DP
给自己至少两周的时间让这些概念在脑子里沉淀。动态规划是需要反刍的知识。
Q：为什么提交 DFS 或记忆化搜索代码会出现 RE？
A：这通常是由于递归深度过大导致栈溢出。系统递归栈的深度有限，当物品数 nn 很大时，递归层数可能超出限制。这正是一个生动的教训：我们学习 DFS 和记忆化是为了理解思想，但在竞赛实战中，必须将其转化为更稳定、高效的迭代 DP 代码。
Q：多重背包的二进制优化为什么有效？
A：其有效性基于一个数学事实：任何正整数都可以由若干个 22 的幂次和一个剩余数组合表示。通过这种拆分，我们将“选择 0∼c0\sim c 个物品”的 O(c)O(c) 次决策，转化为对 O(log⁡c)O(\log c) 个新物品的01背包问题。这本质上是一种“信息压缩”，用更少的状态表达了全部的可能性。
Q：背包问题中最容易忽略的关键点是什么？
A：初始化和状态定义的语义。这直接对应了问题的两种不同要求（以二维数组为例）：
  • 不要求装满：整个 ff 为 00。含义是任何容量的背包，在不装任何物品时价值为 00，且合法。
    这个时候，结果存储在 fn,mf_{n,m}。
  • 要求恰好装满：f0,0=0f_{0,0}=0，其余设为 −∞-\infty。含义是只有容量为 00 的背包能被恰好装满，其他初始状态都不可达。−∞-\infty 保证了所有有效状态都必须从 f0f_0 转移而来，从而确保背包被装满。
    如果题目要求恰好装满，答案就在 fn,mf_{n,m}；如果 fn,m=−∞f_{n,m}=-\infty，则无法将背包恰好装满。
    如果题目不要求装满，答案在 fn,1,fn,2,…,fn,m−1,fn,mf_{n,1},f_{n,2},\dots,f_{n,m-1},f_{n,m} 之中取最大值。

版权声明

本文采用 知识共享 署名-非商业性使用-相同方式共享 4.0 国际 许可协议 进行许可。
您需遵守下列条件：
  • 署名：您必须给出适当的署名，提供指向本许可协议的链接，并标明是否对原始作品作了修改。您可以用任何合理的方式来署名，但不得以任何方式暗示许可人为您或您的使用背书。
  • 非商业性使用：您不得将本作品用于商业目的。
  • 相同方式共享：如果您再混合、转换或者基于本作品进行创作，您必须基于与原先相同的许可协议分发您贡献的作品。

评论

共 4 条评论，欢迎与作者交流。

正在加载评论...