01背包问题是动态规划中最经典的入门问题。它的核心是每种物品只有一件要么选1要么不选0在背包容量有限的情况下让总价值最大。1. 问题描述有N件物品背包容量为V第i件物品重量w[i]价值v[i]每件物品只能选一次求不超过背包容量的最大价值2. 核心思路动态规划定义dp[j] 容量为j的背包能装的最大价值状态转移方程一维优化版textdp[j] max(dp[j], dp[j - w[i]] v[i])不选第i件dp[j]保持不变选第i件容量减少w[i]价值增加v[i]取两者最大值3. 关键注意事项遍历顺序必须从大到小逆序原因一维数组会覆盖历史数据逆序保证dp[j - w[i]]用的是上一轮未选当前物品的状态避免同一件物品被重复选取完全背包才正序。4. C 完整代码cpp#include iostream #include vector #include algorithm using namespace std; int main() { int N, V; cin N V; // 物品数量背包容量 vectorint w(N 1), v(N 1); for (int i 1; i N; i) { cin w[i] v[i]; } // dp[j] 表示容量为 j 的背包能装的最大价值 vectorint dp(V 1, 0); // 遍历每件物品 for (int i 1; i N; i) { // 逆序遍历容量从 V 到 w[i] for (int j V; j w[i]; j--) { dp[j] max(dp[j], dp[j - w[i]] v[i]); } } cout dp[V] endl; return 0; }5. 输入输出示例text输入 4 5 1 2 2 4 3 4 4 5 输出 8选择物品1和3重量134价值246或物品2和3重量235价值4486. 两种写法对比写法数组维度遍历顺序空间复杂度二维dpdp[N1][V1]正序O(NV)一维dp滚动数组dp[V1]容量逆序O(V)一维写法是竞赛中最常用的必须掌握。7. 常见易错点❌ 容量循环写成正序 → 变成完全背包物品可重复选❌ 内层循环从0到V→ 同样错误❌ 忘记初始化dp为 0 → 默认值要保证正确❌ 边界条件j w[i]才更新否则越界8. 扩展如果需要恰好装满初始化时cppdp[0] 0; for (int j 1; j V; j) dp[j] -INF;最后判断dp[V] 0则无法恰好装满。