0/1背包中，每件物品最多选择一次。将二维状态压缩为一维dp数组后，处理重量为w、价值为v的当前物品时，常写成for(c=C;c>=w;c--)。容量从大到小更新的主要原因是（）。
一维压缩后，新旧两层状态共用同一数组。倒序时dp[c-w]还保留处理当前物品之前的值；若正序，较小容量刚写入的新值可能马上被较大容量使用，相当于同一物品选了多次。
选项分析
正确。倒序保证转移来源属于处理当前物品前的状态。
错误。0/1背包允许物品不选，目标通常是容量约束下价值最大。
错误。正序才会形成当前物品可重复使用的完全背包效果。
错误。空间从O(nC)降到O(C)，时间复杂度仍通常为O(nC)。
本题为什么容易错
很多同学只背“01倒、完全正”，一换成具体数组就乱。最可靠的方法是问dp[c-w]应该来自上一件物品处理完的旧层，还是允许来自当前层。
简短答案
0/1背包压缩成一维数组后，容量为什么必须从大到小更新，正确答案是 A（避免本轮刚更新的dp[c-w]再次被使用，从而把同一件物品重复选择）。一维压缩后，新旧两层状态共用同一数组。倒序时dp[c-w]还保留处理当前物品之前的值；若正序，较小容量刚写入的新值可能马上被较大容量使用，相当于同一物品选了多次。
易混淆概念对比表
| 概念 | 本题判断 | 区别要点 | 记忆提示 |
|---|---|---|---|
| 避免本轮刚更新的dp[c-w]再次被使用，从而把同一件物品重复选择 | 本题正确答案 | 正确。倒序保证转移来源属于处理当前物品前的状态。 | 看到题干核心场景时优先联想到它 |
| 保证所有物品都必须被选择 | 本题干扰项 | 错误。0/1背包允许物品不选，目标通常是容量约束下价值最大。 | 看到该词不要急着选，先判断是否真正解决题干问题 |
| 把0/1背包自动改成完全背包 | 本题干扰项 | 错误。正序才会形成当前物品可重复使用的完全背包效果。 | 看到该词不要急着选，先判断是否真正解决题干问题 |
| 使时间复杂度从O(nC)降为O(log C) | 本题干扰项 | 错误。空间从O(nC)降到O(C)，时间复杂度仍通常为O(nC)。 | 看到该词不要急着选，先判断是否真正解决题干问题 |
本题易混淆选项怎么区分
- 保证所有物品都必须被选择：错误。0/1背包允许物品不选，目标通常是容量约束下价值最大。
- 把0/1背包自动改成完全背包：错误。正序才会形成当前物品可重复使用的完全背包效果。
- 使时间复杂度从O(nC)降为O(log C)：错误。空间从O(nC)降到O(C)，时间复杂度仍通常为O(nC)。
知识点详解
二维转移为dp[i][c]=max(dp[i-1][c],dp[i-1][c-w]+v)。压缩后必须确保等式右侧仍读取i-1层。容量倒序可保证较小下标尚未被当前物品更新；完全背包允许使用当前层dp[c-w]，因此可正序。
备考速记
01背包怕拿重，容量倒着走；完全背包能重复，容量顺着走。
倒序枚举在倒序枚举场景中的作用
状态压缩省内存，却也隐藏了新旧层边界。实际编码可以用一个小规模暴力枚举作为对照测试，尤其检查单件物品不能重复和容量边界。
同类题怎么考
- 判断0/1背包一维循环方向。
- 从错误更新结果识别物品被重复使用。
倒序枚举在软件设计师软考中的考法
看到“每件最多一次”先写二维来源，再判断一维数组需要倒序保护旧值；不要直接凭印象选循环方向。
解题思路
拿一件重量3、价值5的物品和容量6试算。若正序，先得到dp[3]=5，更新dp[6]时又读取刚写好的dp[3]，结果变成10，相当于同一件物品拿了两次。倒序先算dp[6]，读到的是上一轮dp[3]，就不会重复。
考点定位
0/1背包一维更新通常倒序，完全背包允许重复选取时通常正序。方向差异来自状态依赖，不是死记的代码格式。
易错提醒
- 外层先枚举容量、内层枚举物品，改变了状态语义。
- 倒序边界写成c> w，漏掉容量恰好等于物品重量的状态。
- 把空间压缩带来的O(C)误写成时间复杂度也降低。
备考提示
- 用单件物品、容量为两倍重量的反例检验循环方向。
- 写转移前先说清dp[c]表示处理到哪一件物品后的最优值。
你可能还想了解
- 0/1背包正序会发生什么？
- 完全背包为什么可以正序？
- 一维dp怎样保证物品只选一次？
本文小结
0/1背包一维化后倒序枚举容量，能保证转移来源仍是上一层状态，避免同一轮重复使用当前物品。