0-1背包问题通过动态规划求解，定义dpi为前i个物品在容量j下的最大价值，转移方程为dpi=max(dpi-1, dpi-1]+v[i-1])，初始状态dp0=0；可用二维数组实现，也可优化为一维数组，从后往前遍历避免覆盖；该思想扩展至完全背包、多重背包等问题。
动态规划（Dynamic Programming，简称 DP）是算法中非常重要的思想，尤其在解决最优化问题时非常有效。背包问题是学习 DP 的经典入门题，帮助理解状态定义、转移方程和边界处理。本文以 0-1 背包为例，带你用 C++ 快速掌握 DP 基础。
什么是 0-1 背包问题？
你有一个容量为 V 的背包，和 n 个物品。每个物品有重量 w[i] 和价值 v[i]。每件物品只能选或不选（即“0 或 1”），目标是让装入背包的物品总价值最大。
输入示例：
n = 4, V = 8
w = [2, 3, 4, 5]
v = [3, 4, 5, 6]
输出：10（选第1、2、4个物品，总重 2+3+5=10？不对，超了。正确组合是第2和第4：3+5=8，价值 4+6=10）
DP 状态设计与转移方程
我们定义：
dp[i][j] 表示前 i 个物品中，背包容量为 j 时能获得的最大价值。
立即学习“C++免费学习笔记（深入）”；
对于第 i 个物品（下标从 1 开始），有两种选择：
- 不选：dp[i][j] = dp[i-1][j]
- 选（前提是 j ≥ w[i-1]）：dp[i][j] = dp[i-1][j - w[i-1]] + v[i-1]
所以转移方程为：
dp[i][j] = max(dp[i-1][j], dp[i-1][j - w[i-1]] + v[i-1])
初始条件：dp[0][j] = 0（没有物品，价值为0）
C++ 实现代码（二维数组版本）
这是最容易理解的写法：
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
<p>int main() {
int n, V;
cin >> n >> V;
vector<int> w(n), v(n);
for (int i = 0; i < n; i++) {
cin >> w[i] >> v[i];
}</p><pre class="brush:php;toolbar:false;">vector<vector<int>> dp(n + 1, vector<int>(V + 1, 0));
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= V; j++) {
dp[i][j] = dp[i-1][j]; // 不选
if (j >= w[i-1]) {
dp[i][j] = max(dp[i][j], dp[i-1][j - w[i-1]] + v[i-1]);
}
}
}
cout << dp[n][V] << endl;
return 0;}
空间优化：一维数组滚动
观察发现：每次只依赖上一行的数据。可以将空间从 O(nV) 降到 O(V)。
关键点：内层循环要从后往前遍历，避免覆盖还未计算的状态。
vector<int> dp(V + 1, 0);
for (int i = 0; i < n; i++) {
for (int j = V; j >= w[i]; j--) {
dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
}
}
cout << dp[V] << endl;
这个版本更简洁，是竞赛常用写法。
常见变种与扩展
- 完全背包：每种物品可选无限次。只需改变内层循环方向：从前往后遍历 j。
- 多重背包：每种物品最多选 m[i] 次。可通过二进制拆分优化成 0-1 背包。
- 分组背包：每组选一个，枚举组 → 枚举容量 → 枚举组内物品。
掌握 0-1 背包，就掌握了 DP 的核心思维方式：拆解问题、定义状态、找出转移关系。
基本上就这些。多写几遍代码，自己推一遍状态转移，很快就能上手。
