背包问题体系（背包九讲）

背包问题从入门到进阶全教程

（适合零基础自学/算法竞赛备考/授课使用，涵盖所有核心考点、坑点、可直接复用模板）

📚 本文定位与学习指南

适用人群

• 刚接触动态规划的零基础学习者

• 准备算法竞赛、校招笔试的考生

• 需要给学生授课的算法老师

学习顺序建议

按照「基础背包→多重背包优化→扩展背包→变种题型」的顺序学习，每学完一个类型先做2~3道模板题巩固，再进入下一部分。

前置知识

只需要掌握基础C++语法、了解数组的基本使用即可，不需要其他前置算法知识。

一、动态规划与背包问题基础

1.1 核心思想

动态规划适用于解决满足重叠子问题、最优子结构的问题：

• 重叠子问题：相同的子问题会重复出现，我们可以把计算结果存起来，避免重复计算

• 最优子结构：全局最优解可以由多个子问题的最优解组合得到 背包问题是动态规划最经典的应用场景，所有变种本质都是基础模型的组合。

1.2 动态规划标准解题五步

所有背包问题都可以遵循以下五步拆解，避免思路混乱：

1. 确定dp数组及下标的含义

2. 推导状态转移（递推）公式

3. 完成dp数组初始化

4. 确定遍历顺序

5. 用小样例推导验证逻辑

二、基础背包模型（入门必学）

2.1 0-1背包（背包问题理论基础）

问题描述

有n件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i]，价值是value[i]。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。

（1）二维DP解法（基础易理解）

样例推导验证

输入：n=3, W=4, weight=[1,3,4], value=[15,90,80]

模板代码（二维版）

#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N = 1e3+10; // 根据题目物品数量调整 ll dp[N][N]; ll T, m; // T=背包总容量，m=物品总数 ll t[N], w[N]; // t[i]=第i个物品重量，w[i]=第i个物品价值 int main(){ cin >> T >> m; dp[0][0] = 0; for(int i=1; i<=m; i++) cin >> t[i] >> w[i]; for(int i=1; i<=m; i++){ for(int j=0; j<=T; j++){ if(j < t[i]) dp[i][j] = dp[i-1][j]; else dp[i][j] = max(dp[i-1][j], dp[i-1][j - t[i]] + w[i]); } } cout << dp[m][T]; return 0; }

（2）一维DP解法（滚动数组优化，刷题首选）

✅优势：空间复杂度从O(n*W)降到O(W)，结果和二维完全一致，是工程/竞赛首选写法。

模板代码（一维版，推荐日常使用）

#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N = 1e3+10; ll dp[N]; ll T, m; ll t[N], w[N]; int main(){ cin >> T >> m; dp[0] = 0; for(int i=1; i<=m; i++) cin >> t[i] >> w[i]; for(int i=1; i<=m; i++){ for(int j=T; j >= t[i]; j--){ // 逆序遍历核心 dp[j] = max(dp[j], dp[j - t[i]] + w[i]); } } cout << dp[T]; return 0; }

2.2 完全背包

问题描述

有n件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i]，价值是value[i]。每件物品可以选无限次，求解将哪些物品装入背包里物品价值总和最大。

（1）二维DP解法（基础易理解）

模板代码（二维版）

#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N = 1e3+10; ll dp[N][N]; ll T, m; ll t[N], w[N]; int main(){ cin >> T >> m; dp[0][0] = 0; for(int i=1; i<=m; i++) cin >> t[i] >> w[i]; for(int i=1; i<=m; i++){ for(int j=0; j<=T; j++){ if(j < t[i]) dp[i][j] = dp[i-1][j]; else dp[i][j] = max(dp[i-1][j], dp[i][j - t[i]] + w[i]); // 和01的唯一差异 } } cout << dp[m][T]; return 0; }

（2）一维DP解法（刷题首选）

✅优势：空间复杂度从O(n*W)降到O(W)，结果和二维完全一致。

模板代码（一维版，推荐日常使用）

#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N = 1e3+10; ll dp[N]; ll T, m; ll t[N], w[N]; int main(){ cin >> T >> m; dp[0] = 0; for(int i=1; i<=m; i++) cin >> t[i] >> w[i]; for(int i=1; i<=m; i++){ for(int j = t[i]; j <= T; j++){ // 正序遍历核心 dp[j] = max(dp[j], dp[j - t[i]] + w[i]); } } cout << dp[T]; return 0; }

2.3 多重背包（暴力基础版）

问题描述

有n种物品和一个容量为W的背包。第i种物品最多有s_i件，每件体积是v_i，价值是w_i。求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。

模板代码（暴力版）

#include<bits/stdc++.h> using namespace std; const int N = 110; int dp[N]; int main(){ int n, m; // n=物品种数，m=背包容量 cin >> n >> m; for(int i=0; i<n; i++){ int v, w, s; // 体积v，价值w，数量s cin >> v >> w >> s; for(int j=m; j >= v; j--){ // 逆序遍历容量 for(int k=1; k <= s && k*v <= j; k++){ // 枚举选k件 dp[j] = max(dp[j], dp[j - k*v] + k*w); } } } cout << dp[m] << endl; return 0; }

三、多重背包进阶优化（中高级考点）

暴力版仅适合小数据，当s_i较大时需要用以下两种优化方案，性能提升非常明显：

3.1 二进制优化（性价比最高，首选用法）

核心原理

利用二进制的「全覆盖特性」：任何正整数S都可以拆分为若干个不重复的2的幂次+一个余数，这些拆分出来的数可以组合出0~S之间的所有整数。 我们把s_i件原物品拆分为若干个新的0-1背包物品：

• 新物品体积 = 原物品体积 × 拆分块大小

• 新物品价值 = 原物品价值 × 拆分块大小 拆分完成后对所有新物品跑0-1背包，结果和原多重背包完全等价，拆分复杂度从O(s_i)降到O(log s_i)。 举个例子：s_i=10，拆分块为1,2,4,3，可以组合出0~10的所有整数： | 要组合的数 | 组合方式 | | --- | --- | | 0 | 不选任何块 | | 1 | 选1 | | 2 | 选2 | | 3 | 1+2 | | 4 | 选4 | | 5 | 4+1 | | 6 | 4+2 | | 7 | 4+2+1 | | 8 | 4+3+1 | | 9 |4+3+2 | |10 |4+3+2+1 | ✅优化效果：s_i=1e5时，暴力需要枚举1e5次，二进制只需要拆17个块，效率提升5000倍以上。

模板代码（适配洛谷P1776 宝物筛选）

#include<bits/stdc++.h> using namespace std; typedef long long ll; const int MAXV = 40010; // 适配题目最大容量4e4 int main(){ int n, W; cin >> n >> W; vector<pair<int, int>> goods; // 存储拆分后的新物品：<重量, 价值> for(int i=0; i<n; i++){ int val, weight, cnt; // 题目输入顺序：价值、重量、数量 cin >> val >> weight >> cnt; // 可选优化：如果cnt件总重量超过背包容量，退化为完全背包直接处理 if(1ll * cnt * weight >= W){ for(int j = weight; j <= W; j += weight){ goods.emplace_back(j, val * (j/weight)); } continue; } // 二进制拆分 for(int k=1; k <= cnt; k *= 2){ goods.emplace_back(weight * k, val * k); cnt -= k; } if(cnt > 0) goods.emplace_back(weight * cnt, val * cnt); // 剩余余数块 } // 统一跑01背包 vector<ll> dp(W+1, 0); for(auto &good : goods){ int w = good.first, v = good.second; for(int j=W; j >= w; j--){ dp[j] = max(dp[j], dp[j - w] + v); } } cout << dp[W] << endl; return 0; }

3.2 单调队列（优先队列）优化（理论最优复杂度）

大家常说的「优先队列优化」其实分为两个版本：

1. 早期原生版本：用大根堆（优先队列）维护滑动窗口最大值，复杂度O(nW log S)，和二进制优化效率差不多，实现麻烦已被淘汰。

2. 主流版本：用单调队列替换大根堆，复杂度降到严格O(nW)，是极限数据场景的最优解。

核心原理

从多重背包原始递推公式变形，按模v（当前物品体积）分组，转化为滑动窗口求最大值问题： 对任意容量j = a*v + r（r是余数），递推公式变形为：d**p[a<e**m>v+r]=(b=ma**x(a−s,0)maxa​(d**p[b</e**m>v+r]−b<e**m>w))+a</e**m>w我们只需要用单调递减的双端队列，维护窗口大小为s+1内的最大值即可，每个元素只会入队出队一次，线性时间完成。

模板代码（适配洛谷P1776 宝物筛选）

#include<bits/stdc++.h> using namespace std; typedef long long ll; const int MAXV = 40010; ll dp[MAXV]; int main() { int n, W; cin >> n >> W; memset(dp, 0, sizeof dp); deque<int> q; // 单调队列存储系数b for (int i = 0; i < n; i++) { int val, weight, cnt; cin >> val >> weight >> cnt; // 退化完全背包优化 if (1ll * cnt * weight >= W) { for (int j = weight; j <= W; j++) dp[j] = max(dp[j], dp[j - weight] + val); continue; } // 按余数0~weight-1分组处理 for (int r = 0; r < weight; r++) { q.clear(); for (int a = 0; a * weight + r <= W; a++) { int j = a * weight + r; int cur_val = dp[j] - 1ll * a * val; // 1. 弹出过期队头 while (!q.empty() && q.front() < a - cnt) q.pop_front(); // 2. 计算当前dp值 if (!q.empty()) { ll max_val = dp[q.front() * weight + r] - 1ll * q.front() * val; dp[j] = max(dp[j], max_val + 1ll * a * val); } // 3. 维护单调队列，插入当前a while (!q.empty() && (dp[q.back() * weight + r] - 1ll * q.back() * val) <= cur_val) q.pop_back(); q.push_back(a); } } } cout << dp[W] << endl; return 0; }

四、扩展背包模型（进阶考点）

4.1 分组背包

问题描述

有N组物品和一个容量为W的背包，每组物品有若干个，同一组内最多只能选1件物品，每件物品有体积和价值，求最大总价值。

模板代码

#include<bits/stdc++.h> using namespace std; const int N = 110; int v[N][N], w[N][N], s[N], dp[N]; // v[i][k]第i组第k个物品体积，s[i]第i组物品数 int main(){ int n, m; // n=分组数，m=背包容量 cin >> n >> m; for(int i=1; i<=n; i++){ cin >> s[i]; for(int j=0; j<s[i]; j++) cin >> v[i][j] >> w[i][j]; } for(int i=1; i<=n; i++){ // 外层遍历分组 for(int j=m; j>=0; j--){ // 中层逆序遍历容量 for(int k=0; k<s[i]; k++){ // 内层遍历组内物品 if(v[i][k] <= j) dp[j] = max(dp[j], dp[j - v[i][k]] + w[i][k]); } } } cout << dp[m] << endl; return 0; }

4.2 混合背包

问题描述

同时包含0-1背包、完全背包、多重背包三种类型的物品，每种物品属于其中一种，求最大总价值。

核心思路

没有新算法，分类处理即可：对每个物品判断类型，调用对应背包的处理逻辑：

模板代码（适配洛谷P1833 樱花）

#include<bits/stdc++.h> using namespace std; const int MAXV = 1010; int dp[MAXV]; int main(){ int n, W; cin >> n >> W; memset(dp, 0, sizeof dp); for(int i=0; i<n; i++){ int v, w, s; // 价值v，重量w，数量s：s=0表示完全背包，s=1表示01背包，s>1表示多重背包 cin >> v >> w >> s; if(s == 0){ // 完全背包：正序 for(int j=w; j<=W; j++) dp[j] = max(dp[j], dp[j-w] + v); }else if(s == 1){ // 01背包：逆序 for(int j=W; j>=w; j--) dp[j] = max(dp[j], dp[j-w] + v); }else{ // 多重背包：二进制拆分 for(int k=1; k<=s; k*=2){ int kw = k*w, kv = k*v; for(int j=W; j>=kw; j--) dp[j] = max(dp[j], dp[j-kw] + kv); s -= k; } if(s>0){ int kw = s*w, kv = s*v; for(int j=W; j>=kw; j--) dp[j] = max(dp[j], dp[j-kw] + kv); } } } cout << dp[W] << endl; return 0; }

4.3 树形背包（树上背包，高阶考点）

问题描述

物品之间构成树形结构，规则是选子节点必须先选父节点，本质是树形DP+分组背包的结合体，典型场景如选课问题：选一门课必须先选它的先修课，求最多选m门课的最大学分。

模板代码（适配洛谷P2014 选课）

#include<bits/stdc++.h> using namespace std; const int MAXN = 310; vector<int> son[MAXN]; // 存储树结构：son[u]是u的所有子节点 int val[MAXN]; // 每个节点的价值 int dp[MAXN][MAXN]; int n, m; void dfs(int u){ dp[u][1] = val[u]; // 只选u自己的情况 for(int v : son[u]){ // 遍历所有子节点 dfs(v); // 先递归处理子树v // 分组背包合并：逆序遍历容量 for(int j=m; j>=1; j--){ // 当前u已经选了j个 for(int k=1; k<j; k++){ // 从子树v选k个 dp[u][j] = max(dp[u][j], dp[u][j-k] + dp[v][k]); } } } } int main(){ cin >> n >> m; m++; // 虚拟根节点占1个位置，原题选m门课，加虚拟根后选m+1个 for(int i=1; i<=n; i++){ int fa, v; cin >> fa >> v; val[i] = v; if(fa == 0) son[0].push_back(i); // 没有先修课的挂在虚拟根0下 else son[fa].push_back(i); } dfs(0); cout << dp[0][m] << endl; return 0; }

📌 附录一：核心背包差异速查表

📌 附录二：常见背包变种与模板

1. 通用递推公式总结

2. 常见变种模板

（1）二维费用背包（同时限制重量和体积）

#include<bits/stdc++.h> using namespace std; const int MAXW = 110, MAXV = 110; int dp[MAXW][MAXV]; // dp[重量][体积] = 最大价值 int main(){ int n, max_w, max_v; cin >> n >> max_w >> max_v; for(int i=0; i<n; i++){ int w, v, val; cin >> w >> v >> val; // 两个维度都逆序遍历，对应01背包逻辑 for(int j = max_w; j >= w; j--){ for(int k = max_v; k >= v; k--){ dp[j][k] = max(dp[j][k], dp[j-w][k-v] + val); } } } cout << dp[max_w][max_v] << endl; return 0; }

（2）背包求具体选择方案（回溯法）

// 用二维dp数组回溯，得到选中的物品编号 vector<int> get_selected(int n, int W, vector<int>& weight, vector<vector<int>>& dp){ vector<int> res; int j = W; for(int i=n; i>=1; i--){ if(dp[i][j] != dp[i-1][j]){ // 说明选了第i个物品 res.push_back(i); j -= weight[i]; } } reverse(res.begin(), res.end()); return res; }

🎯 学习路径与刷题推荐

📝 知识点快速自检表

学完所有内容后可以自查是否掌握核心点：

1. 能说出0-1背包和完全背包的遍历顺序差异及原因？

2. 能解释二进制优化的数学原理？

3. 能说出分组背包的三层遍历顺序及原因？

4. 能区分「组合数」和「排列数」的遍历顺序差异？

5. 能写出树形背包的DFS合并逻辑？ 如果全部能答出，说明你已经完全掌握背包问题的核心考点了~