1. 先搞清楚题目在问什么01背包方案数的识别信号很多同学一看到方案数三个字第一反应是套组合数公式第二反应是DFS枚举。这两种反应本身没问题但放到GESP六级的赛题里大概率会超时。为什么因为01背包求方案数的题目题干往往长得非常像01背包求最大价值的模板题只不过最后一句问法变了很多考生根本没意识到这两者在算法上完全是两条路。我见过的GESP六级真题和模拟题里这类题的典型问法有几种恰好装满容量为V的背包一共有多少种不同的装法在总重量不超过C的前提下有多少种方案背包恰好装满时最大价值对应的方案数是多少注意第三种问法最阴险它把求价值和求方案数揉在一起考如果只会背模板看到这题直接懵。判题的时候很多人能算出最大价值却算不出在最大价值的前提下到底有几种组合方式。先说识别信号。只要题干里出现多少种方案数组合方式搭配方法这类词同时物品有重量且每个物品最多用一次那基本就是01背包求方案数没跑了。如果物品可以重复使用那是完全背包求方案数虽然转移方程长得像但内层循环的方向完全相反后面我会专门说。再有一个隐藏信号题目里如果还带着价值这个维度比如在重量不超过C的情况下能获得的最大价值以及达到该最大价值的方案数那就要警觉。这类题要求你的状态不仅要记录最大值还要记录最大值对应的方案数属于双维度DP比纯方案数多一层逻辑。很多人栽就栽在只维护了价值没维护方案数或者维护方案数时没考虑并列最大的情况。顺便说一句GESP六级对动态规划的考法基本不会出那种一眼就能看出是DP的题。它喜欢场景化包装比如有N种面值的邮票每种只能用一张问能凑出多少种不同的邮资或者有若干根长度不同的木棍从中选几根拼成指定长度问有几种拼接方式。这些全是01背包方案数套了个生活场景的皮。识别本质比背代码重要得多。这里先给结论01背包求方案数的核心代码极短短到让你怀疑它的含金量但它背后的状态定义、初始化逻辑和循环顺序每一项都有讲究少一个条件答案就错。2. 状态设计从选最大值到数方案的思维转换2.1 经典01背包的状态先复习一遍经典的01背包求最大价值状态是这样定义的dp[j] 表示容量为j的背包能装下的最大价值转移方程dp[j] max(dp[j], dp[j - w[i]] v[i]);意思是对于第i个物品要么不装保持原状要么装腾出w[i]的空间加上v[i]的价值两者取大。但求方案数的时候如果你还按取大的思路想就掉进坑里了。为什么因为方案数这个量根本不能用max来聚合。举个例子。容量是5有个物品重量是3。如果最大价值是10那这个10对应的装法可能是A方式也可能是B方式。你要问的是有几种方式能拿到10分而不是10分够不够大。所以方案数必须用加法来聚合。2.2 方案数DP的状态定义求方案数状态定义有两种写法我都说一下。第一种也是最常见的一种状态直接就是方案数本身dp[j] 表示容量为j的背包恰好装满或不超过容量时的方案总数转移方程dp[j] dp[j] dp[j - w[i]];这个式子的含义是当前容量j的方案数 不装第i个物品时已有的方案数dp[j] 装入第i个物品后剩余容量j-w[i]对应的方案数dp[j-w[i]]。这个加法非常好理解但细节在于dp[j-w[i]]里存的到底是什么语义这直接跟初始化挂钩。第二种是价值方案数双维度写法。这种适用于题目既要最大价值又要方案数的场景一般用结构体或两个数组配合struct Node { int value; // 当前容量下的最大价值 long long count; // 达到该最大价值的方案数 };或者分开两个数组int val[V]; // val[j] 表示容量j的最大价值 long long cnt[V]; // cnt[j] 表示容量j且价值为val[j]时的方案数转移时不能只简单加减要分类讨论如果 val[j] val[j-w[i]] v[i]说明装了第i个物品更优那么 val[j] 更新为新的最大值cnt[j] cnt[j-w[i]]如果 val[j] val[j-w[i]] v[i]说明两种装法价值一样那么 cnt[j] cnt[j] cnt[j-w[i]]方案数相加如果 val[j] val[j-w[i]] v[i]什么都不做。你会发现第二种写法里的加法是有前提的只有在价值相等时才相加价值不相等时方案数不能简单相加。这就是并列最优的处理逻辑很多同学的代码错就错在这里不加判断直接加把不优的方案也算进去了。2.3 为什么方案数DP不能用max我用生活化的例子解释一下。假设你手里有1张100元、2张50元你觉得我有3张钱这是数的张数不是数的金额。方案数的本质是有多少种达成方式它的聚合规则天然是加法。而最大值是哪一个更大聚合规则是max。两者完全不同。再往深一层方案数DP其实是在做计数问题它背后是组合计数的乘法原理和加法原理。一个物品选或不选是两条互斥的路径那么总方案数就是两条路径的方案数之和。这也是为什么转移方程里是 dp[j] dp[j-w[i]] 而不是 max。把这条思维理顺了再遇到什么爬楼梯方案数凑零钱方案数都是一回事。3. 核心代码拆解一维滚动数组的正确打开方式3.1 二维递推先把逻辑跑通不急着上优化先用二维数组把逻辑完整推导一遍。定义dp[i][j] 表示前i个物品中挑选若干件恰好装满容量为j的背包的方案数。初始dp[0][0] 1表示0个物品凑出0容量有一种方案啥也不选。 其他 dp[0][j] (j0) 0表示0个物品没有办法凑出正数容量。第i个物品重量 w[i]不选它方案数是 dp[i-1][j]选它前提是 j w[i]方案数是 dp[i-1][j-w[i]]总方案数等于两者之和。所以递推式dp[i][j] dp[i-1][j]; if (j w[i]) dp[i][j] dp[i-1][j-w[i]];我拿一个具体例子手算一遍你就能直观看到这个过程。假设背包容量 W5有3个物品重量分别是 2、3、5暂时不管价值因为纯方案数题不需要价值。初始状态只考虑前0个物品dp[0] [1, 0, 0, 0, 0, 0]下标0到5。处理第1个物品重量2不选dp[1][j] 继承 dp[0][j]选dp[1][2] dp[0][0]即 dp[1][2] 0 1 1。所以 dp[1] [1, 0, 1, 0, 0, 0]。处理第2个物品重量3继承dp[2][j] dp[1][j]选dp[2][3] dp[1][0] 1dp[2][5] dp[1][2] 1。所以 dp[2] [1, 0, 1, 1, 0, 1]。含义是容量3有1种单独物品3容量5有1种物品2物品3。处理第3个物品重量5继承dp[3][j] dp[2][j]选dp[3][5] dp[2][0] 1。所以 dp[3][5] dp[2][5] 1 2。最终 dp[5] 2对应两种方案物品2物品3或者单独物品5。这个手算结果可以用来验证你写的代码对不对非常实用。3.2 压缩成一维关键在循环方向二维写法用来理解一维写法用来过题。一维滚动数组的代码是这样的#include bits/stdc.h using namespace std; const int MAXV 10005; long long dp[MAXV]; int main() { int n, W; cin n W; int w[105]; for (int i 1; i n; i) { cin w[i]; } // 初始化灵魂 dp[0] 1; // 其余 dp[j] 保持为 0 for (int i 1; i n; i) { // 01背包内层必须倒序遍历 for (int j W; j w[i]; j--) { dp[j] dp[j] dp[j - w[i]]; } } cout dp[W] endl; return 0; }这段代码只有十几行但里面有两个最容易写错的地方。第一内层循环必须从 W 倒着到 w[i]。原因和经典01背包一样如果正序遍历dp[j-w[i]] 可能已经在当前物品这一轮被更新过相当于第i个物品被重复使用了这就从01背包变成了完全背包。在方案数问题上这个错误更隐蔽因为结果看起来也有意义但不满足每个物品最多用一次的约束。我见过有同学正着写样例也能过一上大测试点就偏排查半天发现是没倒序。第二dp[0] 1其他是0。这个初始化到底为什么是灵魂我们下一节专门讲。这里先提醒一句千万别以为是dp[0] 0也别以为所有dp[j]初始都应该是1。初始化错了方案数直接翻倍。3.3 复杂度分析01背包方案数的时间复杂度是O(n * W)空间复杂度优化后是O(W)。n是物品数W是背包容量。GESP六级的数据范围物品数一般不超过100容量一般在1000到10000之间这个复杂度在1秒时限内绰绰有余。方案数很容易超过int范围。举例来说100个物品每个重量都是1背包容量是50方案数是C(100, 50)这个数远超int上限。所以建议直接用 long long 存。如果题目明确要求对某个大质数取模那就模运算处理下面会有代码。4. 初始化细节dp[0] 1是灵魂不容商量4.1 两种题型两种初始化初始化不是玄学它决定不可达状态怎么表达。第一种题型恰好装满。这时候 dp[0] 1其余 dp[j] 0。含义是容量为0时有一种方案什么都不选容量大于0但还没开始装物品时任何正容量都无法达到所以方案数为0。递推过程中只有真正能凑到的容量才会被逐步点亮凑不到的保持0。第二种题型不超过容量C。这时候就微妙了。如果你只想求容量不超过C的所有方案总数需要把问题转换一下或者把小于等于C的所有dp[j]加起来。但更常见的写法是仍然采用恰好装满的思路最后累加long long ans 0; for (int j 0; j C; j) ans dp[j];为什么因为不超过容量C的方案其实际占用容量可能是0,1,2,...,C中的任意一个值把这些恰好装满的方案数全部求和就是不超过的方案数。很多题目答案要求输出这个累加值如果直接输出dp[C]会漏掉很多这是高频错误点。这里有个容易绕进去的弯如果把初始化改成所有dp[j] 1含义就变成了任意容量都自带一种方案那显然不对因为它会把凑出该容量和什么都没做混为一谈。所以一律以 dp[0] 1、其余为0作为起点然后根据题目问法决定最后是输出dp[W]还是求和。4.2 再说说恰好装满和不超过容量的场景差异GESP六级更爱考恰好装满。为什么因为它能考察考生对状态语义的理解。比如有N种重量的砝码每种只有一个问能称出多少种不同的重量这是一个典型的恰好装满问题。每种重量j如果能被凑出dp[j] 0最后统计有多少个j满足dp[j] 0。再比如给定一堆物品和一辆载重为W的车问有多少种装货方式如果车没装满也行那就是不超过容量的累加问题。这两种问法和初始化没有直接关系真正区别只在最后的答案汇总方式上。但很多同学的思维定式是求方案数就输出dp[W],结果遇到不超过容量直接丢掉一半方案。4.3 用一维代码实现恰好装满方案数完整可提交的模板#include bits/stdc.h using namespace std; const int MAXV 10005; long long dp[MAXV]; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, W; cin n W; vectorint w(n 1); for (int i 1; i n; i) { cin w[i]; } dp[0] 1; for (int i 1; i n; i) { for (int j W; j w[i]; j--) { dp[j] dp[j - w[i]]; } } cout dp[W] endl; return 0; }如果题目要求取模把 dp 数组初始化和每次加法都取模即可const long long MOD 1000000007; ... dp[j] (dp[j] dp[j - w[i]]) % MOD;4.4 初始化的一个冷门坑用-1初始化不可达状态有些同学在同时求最大价值和方案数时为了区分不可达和方案数为0会先把 dp[j] 初始化为 -1逻辑是-1表示凑不到0表示能凑到但方案数为0。这个想法本身没错但实现的时候很容易忘记在比较时把 -1 的情况特判导致 -1 1 变成 0把不可达状态误判成可达。我的建议是能用 dp[0]1、其余为0 解决就不要引入-1。只有当题目同时要求最大价值且价值本身可能为0比如0价值物品时才考虑用 -1 区分并且转移时记得先判断 dp[j - w[i]] ! -1。能用简单写法就别秀复杂写法比赛里稳才是王道。5. 变体扩展GESP六级里常见的进阶考法5.1 完全背包求方案数区别只有循环方向如果物品可以无限次使用那就是完全背包求方案数。转移方程几乎一样dp[j] dp[j] dp[j - w[i]];唯一区别内层循环从 w[i] 正序遍历到 W。为什么完全背包允许多次选同一个物品正序遍历可以让 dp[j-w[i]] 在本轮更新后再参与计算实现叠加效果。我看到的错误里十有八九是把完全背包的循环方向和01背包搞反。有个很实用的记忆方式同样是求方案数01背包倒序完全背包正序。就这么简单的一个方向决定了整个题目的对错。举个经典变体有若干种面值的硬币每种数量无限问凑出总额N有多少种方案其实就是完全背包方案数也叫换零钱问题。它的代码和01背包方案数就差一个循环方向。5.2 最大价值 方案数双维度为了说清楚这个变体我拿一个具体的题目场景来演示。假设背包容量 W5物品重量和价值分别是(2,3)、(3,4)、(1,2)求恰好装满容量5的最大价值以及达到该最大价值的方案数。先手算可能的装满组合有——物1(2)物2(3)总重5总价7物1(2)物3(1)物3(1)不行每个物品只能用一次。物2(3)物3(1)物3(1)不行。物2(3)物1(2)同上。物3(1)要装满5得凑5个物3但物3只有一个。物1(2)物3(1)只有重量3填不满。物2(3)物3(1)重量4填不满。所以唯一装满容量5的方案是物1物2最大价值7方案数1。但如果把物品改成(1,2)、(2,3)、(3,4)容量5组合1123总重6超了。组合212总重3不行。组合3122不行物品2只有一个。组合423总重5价值7。组合511不行物品1只有一个。组合613总重4不行。 结果还是1种。再设计一个并列最优的例子(2,5)、(3,5)、(5,10)背包容量5。重量恰好装满5的组合有(23) 价值10(5) 价值10。两条路价值并列都是10。这时候方案数就是2。这类题就是靠并列最优拉区分度的。双维度实现的代码思路如下#include bits/stdc.h using namespace std; const int MAXV 10005; long long val[MAXV]; // 容量j的最大价值 long long cnt[MAXV]; // 容量j达到最大价值的方案数 const long long MOD 1000000007; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, W; cin n W; vectorint w(n 1), v(n 1); for (int i 1; i n; i) cin w[i] v[i]; cnt[0] 1; // 容量0价值0有一种方案 for (int i 1; i n; i) { for (int j W; j w[i]; j--) { long long newValue val[j - w[i]] v[i]; if (newValue val[j]) { val[j] newValue; cnt[j] cnt[j - w[i]] % MOD; } else if (newValue val[j]) { cnt[j] (cnt[j] cnt[j - w[i]]) % MOD; } } } cout val[W] cnt[W] % MOD endl; return 0; }注意几个细节当新价值更大时cnt[j] 直接覆盖成 cnt[j-w[i]]而不是累加当价值相等时cnt[j] 累加。这个逻辑对应了最大价值变化时方案数重置最大价值并列时方案数合并是整个代码的精髓。另外这个代码默认了任何容量从0到W都是可达的但实际中有些容量凑不到val[j] 会一直是0cnt[j] 也会是0不影响结果。如果物品价值可能是0那就需要把 val 初始化为一个极小值同时 cnt[0] 1才能在严格意义上区分可达但价值为0和不可达。考场上有时间就处理没时间就先按上述模板多数测试点不会卡这个边界。5.3 二维费用背包方案数GESP六级偶尔会出现二维限制比如每个物品有重量和体积两种限制背包有容量和体积两个上限问方案数。这种题要开二维状态dp[j][k] 表示容量为j、体积为k时的方案数转移dp[j][k] dp[j - w[i]][k - c[i]];维度多了一维复杂度也上来。好在GESP六级对这类题的数据范围都不大30个物品以内、容量百位级可以接受。二维费用的关键是初始化仍然是 dp[0][0] 1其余为0。循环方向注意两维都要倒序。写起来不难但要注意数组别越界内层循环的边界判断要完整。6. 常见问题与排查技巧实录6.1 高频Bug速查表错误类型具体表现解决方案循环方向写反每个物品被重复使用方案数偏大01背包内层倒序完全背包内层正序初始化错误dp[0]设成0导致所有方案数从源头丢失dp[0] 1其他为0价值方案数并列没判等最大价值并列时方案数漏加转移时分 newValue val[j] 和 两种情况没用 long long方案数爆int输出负数或截断全部改成 long long输出dp[W]但题目要不超过容量漏算容量不满的方案累加所有 dp[0] 到 dp[W]用DFS枚举替代DP物品数稍大就超时识别背包模型直接用DP忘记判断 j w[i]数组越界或负下标内层循环起点定为 w[i]以上每一项我都见过真实案例。特别是输出dp[W]但题目要不超过容量这个坑GESP六级的模拟题里出现过不少考生当场丢分。6.2 排错实战一个经典翻车现场有一次我帮一个学生排查他写的代码样例能过但提交到评测系统就WA。我让他打印中间dp数组发现在处理第2个物品时容量3的dp值变成了2而手算是1。仔细一看他内层循环写的是正序。正序时处理重量3的物品dp[3] dp[3] dp[0] 1没问题但紧接着 j 增大到6时dp[6] dp[6] dp[3]这个 dp[3] 已经被本轮更新过导致第2个物品被使用两次。物品数少、容量小时看不出来容量一大错误就累积。这个案例告诉我们一个排错思路先用小数据手算把每一轮dp数组的期望值列出来再打印程序里每一轮的dp数组做对比。第一轮不匹配说明初始化或外层循环有问题第几轮开始不匹配说明那一轮的物品处理有问题。这个方法比盯着代码干想有效得多。还有一个调试技巧把 dp[j] 的更新打印出来看看每次是从哪个 dp[j-w[i]] 转移来的。如果是正序导致的重复使用你会发现 dp[j-w[i]] 出现本轮已更新的新值一抓一个准。6.3 考场策略什么时候用二维什么时候贪省事我个人的习惯是在草稿纸上先用二维思路写递推关系确认状态转移没有逻辑漏洞后再压缩成一维写代码。直接上手一维如果错了很难定位是压缩过程出错还是算法本身出错。二维的代码虽然空间复杂度差一点但逻辑直观、不容易写出歧义数据范围小时直接交二维也能过。如果内存卡得紧再用一维。转换过程有个检查点把二维代码中的 dp[i-1] 全部替换成 dp 本身的当前值然后看循环方向是否需要调整。01背包倒序、完全背包正序记住这一点一维压缩基本不会出错。另外提醒一点GESP六级环境里的编译器默认是C14long long在64位机器上是8字节足够存一般方案数。但如果题目方案数极大且不要求取模long long也可能爆掉。遇到这种题要么用 __int128要么按题目要求及时取模。以GESP六级的数据范围看long long 基本都够。7. 一点实战心得带过不少学生复习GESP六级我发现01背包方案数这块的失分很少是不会写转移方程更多是条件反射式套模板带来的低级错误。写模板前花三十秒问自己三个问题第一物品能重复用吗第二背包要恰好装满还是不超过容量第三题目要不要关心最大价值三个问题想清楚代码基本就已经对了一半。我自己复习动态规划时有个习惯每学一种模型就亲手在小黑板上推导一遍二维递推再压成一维最后用随机小数据和暴力DFS对拍验证。这个过程看着慢但能把模型吃透后期遇到变形题根本不用硬记代码。01背包求方案数、完全背包求方案数、爬楼梯、凑零钱本质上都共用同一套加法计数的思维框架你把它理解成一棵选择树的节点计数什么变体都逃不出这个逻辑。最后分享一个小技巧考试时如果实在不确定循环方向就在草稿纸上画一个5列的小表格手动推两个物品的dp过程方向对了结果自然对方向错了5分钟就能发现。别嫌麻烦这比反复编译提交省时间得多。 
长河君 · 2026/10/10 21:52:48 · 阅读 1.2k 01背包方案数全解析：从状态设计到代码实现
1. 先搞清楚题目在问什么01背包方案数的识别信号很多同学一看到方案数三个字第一反应是套组合数公式第二反应是DFS枚举。这两种反应本身没问题但放到GESP六级的赛题里大概率会超时。为什么因为01背包求方案数的题目题干往往长得非常像01背包求最大价值的模板题只不过最后一句问法变了很多考生根本没意识到这两者在算法上完全是两条路。我见过的GESP六级真题和模拟题里这类题的典型问法有几种恰好装满容量为V的背包一共有多少种不同的装法在总重量不超过C的前提下有多少种方案背包恰好装满时最大价值对应的方案数是多少注意第三种问法最阴险它把求价值和求方案数揉在一起考如果只会背模板看到这题直接懵。判题的时候很多人能算出最大价值却算不出在最大价值的前提下到底有几种组合方式。先说识别信号。只要题干里出现多少种方案数组合方式搭配方法这类词同时物品有重量且每个物品最多用一次那基本就是01背包求方案数没跑了。如果物品可以重复使用那是完全背包求方案数虽然转移方程长得像但内层循环的方向完全相反后面我会专门说。再有一个隐藏信号题目里如果还带着价值这个维度比如在重量不超过C的情况下能获得的最大价值以及达到该最大价值的方案数那就要警觉。这类题要求你的状态不仅要记录最大值还要记录最大值对应的方案数属于双维度DP比纯方案数多一层逻辑。很多人栽就栽在只维护了价值没维护方案数或者维护方案数时没考虑并列最大的情况。顺便说一句GESP六级对动态规划的考法基本不会出那种一眼就能看出是DP的题。它喜欢场景化包装比如有N种面值的邮票每种只能用一张问能凑出多少种不同的邮资或者有若干根长度不同的木棍从中选几根拼成指定长度问有几种拼接方式。这些全是01背包方案数套了个生活场景的皮。识别本质比背代码重要得多。这里先给结论01背包求方案数的核心代码极短短到让你怀疑它的含金量但它背后的状态定义、初始化逻辑和循环顺序每一项都有讲究少一个条件答案就错。2. 状态设计从选最大值到数方案的思维转换2.1 经典01背包的状态先复习一遍经典的01背包求最大价值状态是这样定义的dp[j] 表示容量为j的背包能装下的最大价值转移方程dp[j] max(dp[j], dp[j - w[i]] v[i]);意思是对于第i个物品要么不装保持原状要么装腾出w[i]的空间加上v[i]的价值两者取大。但求方案数的时候如果你还按取大的思路想就掉进坑里了。为什么因为方案数这个量根本不能用max来聚合。举个例子。容量是5有个物品重量是3。如果最大价值是10那这个10对应的装法可能是A方式也可能是B方式。你要问的是有几种方式能拿到10分而不是10分够不够大。所以方案数必须用加法来聚合。2.2 方案数DP的状态定义求方案数状态定义有两种写法我都说一下。第一种也是最常见的一种状态直接就是方案数本身dp[j] 表示容量为j的背包恰好装满或不超过容量时的方案总数转移方程dp[j] dp[j] dp[j - w[i]];这个式子的含义是当前容量j的方案数 不装第i个物品时已有的方案数dp[j] 装入第i个物品后剩余容量j-w[i]对应的方案数dp[j-w[i]]。这个加法非常好理解但细节在于dp[j-w[i]]里存的到底是什么语义这直接跟初始化挂钩。第二种是价值方案数双维度写法。这种适用于题目既要最大价值又要方案数的场景一般用结构体或两个数组配合struct Node { int value; // 当前容量下的最大价值 long long count; // 达到该最大价值的方案数 };或者分开两个数组int val[V]; // val[j] 表示容量j的最大价值 long long cnt[V]; // cnt[j] 表示容量j且价值为val[j]时的方案数转移时不能只简单加减要分类讨论如果 val[j] val[j-w[i]] v[i]说明装了第i个物品更优那么 val[j] 更新为新的最大值cnt[j] cnt[j-w[i]]如果 val[j] val[j-w[i]] v[i]说明两种装法价值一样那么 cnt[j] cnt[j] cnt[j-w[i]]方案数相加如果 val[j] val[j-w[i]] v[i]什么都不做。你会发现第二种写法里的加法是有前提的只有在价值相等时才相加价值不相等时方案数不能简单相加。这就是并列最优的处理逻辑很多同学的代码错就错在这里不加判断直接加把不优的方案也算进去了。2.3 为什么方案数DP不能用max我用生活化的例子解释一下。假设你手里有1张100元、2张50元你觉得我有3张钱这是数的张数不是数的金额。方案数的本质是有多少种达成方式它的聚合规则天然是加法。而最大值是哪一个更大聚合规则是max。两者完全不同。再往深一层方案数DP其实是在做计数问题它背后是组合计数的乘法原理和加法原理。一个物品选或不选是两条互斥的路径那么总方案数就是两条路径的方案数之和。这也是为什么转移方程里是 dp[j] dp[j-w[i]] 而不是 max。把这条思维理顺了再遇到什么爬楼梯方案数凑零钱方案数都是一回事。3. 核心代码拆解一维滚动数组的正确打开方式3.1 二维递推先把逻辑跑通不急着上优化先用二维数组把逻辑完整推导一遍。定义dp[i][j] 表示前i个物品中挑选若干件恰好装满容量为j的背包的方案数。初始dp[0][0] 1表示0个物品凑出0容量有一种方案啥也不选。 其他 dp[0][j] (j0) 0表示0个物品没有办法凑出正数容量。第i个物品重量 w[i]不选它方案数是 dp[i-1][j]选它前提是 j w[i]方案数是 dp[i-1][j-w[i]]总方案数等于两者之和。所以递推式dp[i][j] dp[i-1][j]; if (j w[i]) dp[i][j] dp[i-1][j-w[i]];我拿一个具体例子手算一遍你就能直观看到这个过程。假设背包容量 W5有3个物品重量分别是 2、3、5暂时不管价值因为纯方案数题不需要价值。初始状态只考虑前0个物品dp[0] [1, 0, 0, 0, 0, 0]下标0到5。处理第1个物品重量2不选dp[1][j] 继承 dp[0][j]选dp[1][2] dp[0][0]即 dp[1][2] 0 1 1。所以 dp[1] [1, 0, 1, 0, 0, 0]。处理第2个物品重量3继承dp[2][j] dp[1][j]选dp[2][3] dp[1][0] 1dp[2][5] dp[1][2] 1。所以 dp[2] [1, 0, 1, 1, 0, 1]。含义是容量3有1种单独物品3容量5有1种物品2物品3。处理第3个物品重量5继承dp[3][j] dp[2][j]选dp[3][5] dp[2][0] 1。所以 dp[3][5] dp[2][5] 1 2。最终 dp[5] 2对应两种方案物品2物品3或者单独物品5。这个手算结果可以用来验证你写的代码对不对非常实用。3.2 压缩成一维关键在循环方向二维写法用来理解一维写法用来过题。一维滚动数组的代码是这样的#include bits/stdc.h using namespace std; const int MAXV 10005; long long dp[MAXV]; int main() { int n, W; cin n W; int w[105]; for (int i 1; i n; i) { cin w[i]; } // 初始化灵魂 dp[0] 1; // 其余 dp[j] 保持为 0 for (int i 1; i n; i) { // 01背包内层必须倒序遍历 for (int j W; j w[i]; j--) { dp[j] dp[j] dp[j - w[i]]; } } cout dp[W] endl; return 0; }这段代码只有十几行但里面有两个最容易写错的地方。第一内层循环必须从 W 倒着到 w[i]。原因和经典01背包一样如果正序遍历dp[j-w[i]] 可能已经在当前物品这一轮被更新过相当于第i个物品被重复使用了这就从01背包变成了完全背包。在方案数问题上这个错误更隐蔽因为结果看起来也有意义但不满足每个物品最多用一次的约束。我见过有同学正着写样例也能过一上大测试点就偏排查半天发现是没倒序。第二dp[0] 1其他是0。这个初始化到底为什么是灵魂我们下一节专门讲。这里先提醒一句千万别以为是dp[0] 0也别以为所有dp[j]初始都应该是1。初始化错了方案数直接翻倍。3.3 复杂度分析01背包方案数的时间复杂度是O(n * W)空间复杂度优化后是O(W)。n是物品数W是背包容量。GESP六级的数据范围物品数一般不超过100容量一般在1000到10000之间这个复杂度在1秒时限内绰绰有余。方案数很容易超过int范围。举例来说100个物品每个重量都是1背包容量是50方案数是C(100, 50)这个数远超int上限。所以建议直接用 long long 存。如果题目明确要求对某个大质数取模那就模运算处理下面会有代码。4. 初始化细节dp[0] 1是灵魂不容商量4.1 两种题型两种初始化初始化不是玄学它决定不可达状态怎么表达。第一种题型恰好装满。这时候 dp[0] 1其余 dp[j] 0。含义是容量为0时有一种方案什么都不选容量大于0但还没开始装物品时任何正容量都无法达到所以方案数为0。递推过程中只有真正能凑到的容量才会被逐步点亮凑不到的保持0。第二种题型不超过容量C。这时候就微妙了。如果你只想求容量不超过C的所有方案总数需要把问题转换一下或者把小于等于C的所有dp[j]加起来。但更常见的写法是仍然采用恰好装满的思路最后累加long long ans 0; for (int j 0; j C; j) ans dp[j];为什么因为不超过容量C的方案其实际占用容量可能是0,1,2,...,C中的任意一个值把这些恰好装满的方案数全部求和就是不超过的方案数。很多题目答案要求输出这个累加值如果直接输出dp[C]会漏掉很多这是高频错误点。这里有个容易绕进去的弯如果把初始化改成所有dp[j] 1含义就变成了任意容量都自带一种方案那显然不对因为它会把凑出该容量和什么都没做混为一谈。所以一律以 dp[0] 1、其余为0作为起点然后根据题目问法决定最后是输出dp[W]还是求和。4.2 再说说恰好装满和不超过容量的场景差异GESP六级更爱考恰好装满。为什么因为它能考察考生对状态语义的理解。比如有N种重量的砝码每种只有一个问能称出多少种不同的重量这是一个典型的恰好装满问题。每种重量j如果能被凑出dp[j] 0最后统计有多少个j满足dp[j] 0。再比如给定一堆物品和一辆载重为W的车问有多少种装货方式如果车没装满也行那就是不超过容量的累加问题。这两种问法和初始化没有直接关系真正区别只在最后的答案汇总方式上。但很多同学的思维定式是求方案数就输出dp[W],结果遇到不超过容量直接丢掉一半方案。4.3 用一维代码实现恰好装满方案数完整可提交的模板#include bits/stdc.h using namespace std; const int MAXV 10005; long long dp[MAXV]; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, W; cin n W; vectorint w(n 1); for (int i 1; i n; i) { cin w[i]; } dp[0] 1; for (int i 1; i n; i) { for (int j W; j w[i]; j--) { dp[j] dp[j - w[i]]; } } cout dp[W] endl; return 0; }如果题目要求取模把 dp 数组初始化和每次加法都取模即可const long long MOD 1000000007; ... dp[j] (dp[j] dp[j - w[i]]) % MOD;4.4 初始化的一个冷门坑用-1初始化不可达状态有些同学在同时求最大价值和方案数时为了区分不可达和方案数为0会先把 dp[j] 初始化为 -1逻辑是-1表示凑不到0表示能凑到但方案数为0。这个想法本身没错但实现的时候很容易忘记在比较时把 -1 的情况特判导致 -1 1 变成 0把不可达状态误判成可达。我的建议是能用 dp[0]1、其余为0 解决就不要引入-1。只有当题目同时要求最大价值且价值本身可能为0比如0价值物品时才考虑用 -1 区分并且转移时记得先判断 dp[j - w[i]] ! -1。能用简单写法就别秀复杂写法比赛里稳才是王道。5. 变体扩展GESP六级里常见的进阶考法5.1 完全背包求方案数区别只有循环方向如果物品可以无限次使用那就是完全背包求方案数。转移方程几乎一样dp[j] dp[j] dp[j - w[i]];唯一区别内层循环从 w[i] 正序遍历到 W。为什么完全背包允许多次选同一个物品正序遍历可以让 dp[j-w[i]] 在本轮更新后再参与计算实现叠加效果。我看到的错误里十有八九是把完全背包的循环方向和01背包搞反。有个很实用的记忆方式同样是求方案数01背包倒序完全背包正序。就这么简单的一个方向决定了整个题目的对错。举个经典变体有若干种面值的硬币每种数量无限问凑出总额N有多少种方案其实就是完全背包方案数也叫换零钱问题。它的代码和01背包方案数就差一个循环方向。5.2 最大价值 方案数双维度为了说清楚这个变体我拿一个具体的题目场景来演示。假设背包容量 W5物品重量和价值分别是(2,3)、(3,4)、(1,2)求恰好装满容量5的最大价值以及达到该最大价值的方案数。先手算可能的装满组合有——物1(2)物2(3)总重5总价7物1(2)物3(1)物3(1)不行每个物品只能用一次。物2(3)物3(1)物3(1)不行。物2(3)物1(2)同上。物3(1)要装满5得凑5个物3但物3只有一个。物1(2)物3(1)只有重量3填不满。物2(3)物3(1)重量4填不满。所以唯一装满容量5的方案是物1物2最大价值7方案数1。但如果把物品改成(1,2)、(2,3)、(3,4)容量5组合1123总重6超了。组合212总重3不行。组合3122不行物品2只有一个。组合423总重5价值7。组合511不行物品1只有一个。组合613总重4不行。 结果还是1种。再设计一个并列最优的例子(2,5)、(3,5)、(5,10)背包容量5。重量恰好装满5的组合有(23) 价值10(5) 价值10。两条路价值并列都是10。这时候方案数就是2。这类题就是靠并列最优拉区分度的。双维度实现的代码思路如下#include bits/stdc.h using namespace std; const int MAXV 10005; long long val[MAXV]; // 容量j的最大价值 long long cnt[MAXV]; // 容量j达到最大价值的方案数 const long long MOD 1000000007; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, W; cin n W; vectorint w(n 1), v(n 1); for (int i 1; i n; i) cin w[i] v[i]; cnt[0] 1; // 容量0价值0有一种方案 for (int i 1; i n; i) { for (int j W; j w[i]; j--) { long long newValue val[j - w[i]] v[i]; if (newValue val[j]) { val[j] newValue; cnt[j] cnt[j - w[i]] % MOD; } else if (newValue val[j]) { cnt[j] (cnt[j] cnt[j - w[i]]) % MOD; } } } cout val[W] cnt[W] % MOD endl; return 0; }注意几个细节当新价值更大时cnt[j] 直接覆盖成 cnt[j-w[i]]而不是累加当价值相等时cnt[j] 累加。这个逻辑对应了最大价值变化时方案数重置最大价值并列时方案数合并是整个代码的精髓。另外这个代码默认了任何容量从0到W都是可达的但实际中有些容量凑不到val[j] 会一直是0cnt[j] 也会是0不影响结果。如果物品价值可能是0那就需要把 val 初始化为一个极小值同时 cnt[0] 1才能在严格意义上区分可达但价值为0和不可达。考场上有时间就处理没时间就先按上述模板多数测试点不会卡这个边界。5.3 二维费用背包方案数GESP六级偶尔会出现二维限制比如每个物品有重量和体积两种限制背包有容量和体积两个上限问方案数。这种题要开二维状态dp[j][k] 表示容量为j、体积为k时的方案数转移dp[j][k] dp[j - w[i]][k - c[i]];维度多了一维复杂度也上来。好在GESP六级对这类题的数据范围都不大30个物品以内、容量百位级可以接受。二维费用的关键是初始化仍然是 dp[0][0] 1其余为0。循环方向注意两维都要倒序。写起来不难但要注意数组别越界内层循环的边界判断要完整。6. 常见问题与排查技巧实录6.1 高频Bug速查表错误类型具体表现解决方案循环方向写反每个物品被重复使用方案数偏大01背包内层倒序完全背包内层正序初始化错误dp[0]设成0导致所有方案数从源头丢失dp[0] 1其他为0价值方案数并列没判等最大价值并列时方案数漏加转移时分 newValue val[j] 和 两种情况没用 long long方案数爆int输出负数或截断全部改成 long long输出dp[W]但题目要不超过容量漏算容量不满的方案累加所有 dp[0] 到 dp[W]用DFS枚举替代DP物品数稍大就超时识别背包模型直接用DP忘记判断 j w[i]数组越界或负下标内层循环起点定为 w[i]以上每一项我都见过真实案例。特别是输出dp[W]但题目要不超过容量这个坑GESP六级的模拟题里出现过不少考生当场丢分。6.2 排错实战一个经典翻车现场有一次我帮一个学生排查他写的代码样例能过但提交到评测系统就WA。我让他打印中间dp数组发现在处理第2个物品时容量3的dp值变成了2而手算是1。仔细一看他内层循环写的是正序。正序时处理重量3的物品dp[3] dp[3] dp[0] 1没问题但紧接着 j 增大到6时dp[6] dp[6] dp[3]这个 dp[3] 已经被本轮更新过导致第2个物品被使用两次。物品数少、容量小时看不出来容量一大错误就累积。这个案例告诉我们一个排错思路先用小数据手算把每一轮dp数组的期望值列出来再打印程序里每一轮的dp数组做对比。第一轮不匹配说明初始化或外层循环有问题第几轮开始不匹配说明那一轮的物品处理有问题。这个方法比盯着代码干想有效得多。还有一个调试技巧把 dp[j] 的更新打印出来看看每次是从哪个 dp[j-w[i]] 转移来的。如果是正序导致的重复使用你会发现 dp[j-w[i]] 出现本轮已更新的新值一抓一个准。6.3 考场策略什么时候用二维什么时候贪省事我个人的习惯是在草稿纸上先用二维思路写递推关系确认状态转移没有逻辑漏洞后再压缩成一维写代码。直接上手一维如果错了很难定位是压缩过程出错还是算法本身出错。二维的代码虽然空间复杂度差一点但逻辑直观、不容易写出歧义数据范围小时直接交二维也能过。如果内存卡得紧再用一维。转换过程有个检查点把二维代码中的 dp[i-1] 全部替换成 dp 本身的当前值然后看循环方向是否需要调整。01背包倒序、完全背包正序记住这一点一维压缩基本不会出错。另外提醒一点GESP六级环境里的编译器默认是C14long long在64位机器上是8字节足够存一般方案数。但如果题目方案数极大且不要求取模long long也可能爆掉。遇到这种题要么用 __int128要么按题目要求及时取模。以GESP六级的数据范围看long long 基本都够。7. 一点实战心得带过不少学生复习GESP六级我发现01背包方案数这块的失分很少是不会写转移方程更多是条件反射式套模板带来的低级错误。写模板前花三十秒问自己三个问题第一物品能重复用吗第二背包要恰好装满还是不超过容量第三题目要不要关心最大价值三个问题想清楚代码基本就已经对了一半。我自己复习动态规划时有个习惯每学一种模型就亲手在小黑板上推导一遍二维递推再压成一维最后用随机小数据和暴力DFS对拍验证。这个过程看着慢但能把模型吃透后期遇到变形题根本不用硬记代码。01背包求方案数、完全背包求方案数、爬楼梯、凑零钱本质上都共用同一套加法计数的思维框架你把它理解成一棵选择树的节点计数什么变体都逃不出这个逻辑。最后分享一个小技巧考试时如果实在不确定循环方向就在草稿纸上画一个5列的小表格手动推两个物品的dp过程方向对了结果自然对方向错了5分钟就能发现。别嫌麻烦这比反复编译提交省时间得多。