在竞赛编程中，经常遇到动态规划问题，比如“最长上升子序列”或“背包问题”。请用C++实现一个动态规划算法解决“01背包问题”，并分析时间复杂度，以及如何优化空间复杂度（如滚动数组）。
学而思竞赛教练：理科、编程 (C++)难度：中等
答案
1) 【一句话结论】：01背包问题可通过动态规划解决，定义状态dp[j]为容量为j时最大价值，状态转移为dp[j] = max(dp[j], dp[j - w[i]] + v[i])（j≥w[i]），时间复杂度O(n*V)，空间优化后用滚动数组降为O(V)。
2) 【原理/概念讲解】：01背包属于“0-1”选择问题，即每个物品（重量w[i]、价值v[i]）只能选或不选。动态规划的核心是“状态定义”和“状态转移”。
- 状态定义：设
dp[j]表示当前背包容量为j时，能获得的最大总价值。 - 状态转移：对于第
i个物品，若不选，dp[j]保持原值；若选（需满足j≥w[i]），则更新为原值与“选当前物品后”的值（dp[j - w[i]] + v[i]）的最大值。
类比：就像装背包，每个物品要么放（选）要么不放（不选），类似二进制选择，状态转移时考虑是否“加入”当前物品对总价值的影响。
3) 【对比与适用场景】：
| 特性 | 01背包（物品不可重复） | 完全背包（物品可重复） |
|---|---|---|
| 定义 | n个物品，每个物品选0或1个 | n个物品，每个物品可重复选 |
| 状态转移 | dp[j] = max(dp[j], dp[j-w[i]]+v[i]) | dp[j] = max(dp[j], dp[j-w[i]]+v[i])（累加） |
| 使用场景 | 选不同物品（如选不同商品） | 选相同物品（如选硬币） |
| 注意点 | j≥w[i]时才考虑选当前物品 | 无额外限制，直接累加 |
4) 【示例】：假设有3个物品，重量[2,3,4]，价值[3,4,5]，背包容量V=5。计算过程：
- 初始化
dp数组为0（容量0时价值为0）。 - 遍历物品：
- 物品1（
w=2,v=3）：j从2到5，dp[j] = max(dp[j], dp[j-2]+3)→ 最终dp=[0,3,3,3,3]。 - 物品2（
w=3,v=4）：j从3到5，dp[3]=max(3, dp[0]+4)=4，dp[4]=max(3, dp[1]+4)=4，dp[5]=max(3, dp[2]+4)=7。 - 物品3（
w=4,v=5）：j从4到5，dp[4]=max(4, dp[0]+5)=5，dp[5]=max(7, dp[1]+5)=7。
最终dp[5]=7，最大价值为7。
- 物品1（
代码（C++伪代码）：
int zeroOneKnapsack(vector<int> weight, vector<int> value, int V) {
vector<int> dp(V + 1, 0);
for (int i = 0; i < weight.size(); ++i) {
for (int j = V; j >= weight[i]; --j) {
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
}
}
return dp[V];
}
5) 【面试口播版答案】：您好，01背包问题可以用动态规划解决。核心思路是定义状态dp[j]表示背包容量为j时能获得的最大价值，状态转移方程为dp[j] = max(dp[j], dp[j - weight[i]] + value[i])（当j≥weight[i]时才考虑选当前物品）。时间复杂度是O(n*V)，因为需要遍历所有物品和所有容量。为了优化空间，可以用一维数组滚动，即只保留前一列的dp值，这样空间复杂度降为O(V)。具体实现时，外层循环遍历物品，内层循环从后往前更新dp数组，避免重复计算。例如，对于物品重量[2,3,4]，价值[3,4,5]，容量5，最终最大价值为7。代码实现就是上述的循环结构，时间复杂度O(n*V)，空间优化后O(V)。
6) 【追问清单】：
- 问：为什么01背包的空间可以优化为一维数组？
回答要点：因为状态转移只依赖于前一列的dp值（即当前容量j的值只由j-w[i]的值决定），所以可以用滚动数组，只保留一维数组即可。 - 问：完全背包和01背包的区别是什么？
回答要点：01背包物品不可重复选，完全背包可重复选，转移方程不同（完全背包内层循环从前往后，累加当前物品的价值）。 - 问：如果物品数量很大（如
n=10^5），容量V=10^3，如何优化？
回答要点：对于01背包，滚动数组已经是空间优化，时间复杂度O(n*V)可能较高，若V较小，可接受；若n和V都很大，可能需要更高效的算法，如二分查找或预处理，但基础是状态转移的正确性。 - 问：动态规划是否适用于所有背包问题？
回答要点：是的，背包问题（0-1、完全、多重背包等）都可以用动态规划解决，只是状态转移和边界条件不同，多重背包需要处理物品数量限制，可能需要优化转移（如记忆化搜索或优化DP）。
7) 【常见坑/雷区】：
- 状态转移时忘记
j≥weight[i]的条件，导致数组越界或计算错误（如j<weight[i]时尝试减重量，导致负数或错误值）。 - 空间优化时数组更新顺序错误，比如内层循环从前往后，导致当前
dp[j]依赖更新后的值，应从后往前更新。 - 混淆01背包和完全背包的转移方程，导致结果错误（如完全背包内层循环从前往后，01背包从后往前）。
- 时间复杂度分析错误，误认为
O(n²)而实际是O(n*V)，或忽略内层循环的次数。 - 初始化
dp数组时错误，比如初始化为-1或负数，导致后续计算错误（应初始化为0，因为容量为0时价值为0）。