GESP 六级 · GESP 202512 C++ 六级 第 14 题

0/1 背包（每件物品最多选一次）问题通常可用一维动态规划求解，核心代码如下。则下面说法正确的是（ ）。

for each item (w, v):
    for (int j = W; j >= w; --j)
        dp[j] = max(dp[j], dp[j-w] + v);

背包问题：01背包倒序枚举容量，完全背包正序枚举容量。状态 dp[i][j] 表示前i个物品容量j的最大价值。

01背包内层循环必须从大到小枚举容量，保证每个物品只用一次。完全背包从小到大枚举，物品可用无限次。

【考点】0/1背包一维优化｜DP状态转移方向｜空间压缩陷阱

GESP六级DP模块核心题，90%考生卡在"一维化后方向为何必须倒序"上。命题人专挑空间优化陷阱，因为二维转一维是六级必考，但方向错误会导致完全背包解法混入，直接丢分。

先想二维dp[i][j]表示前i件、容量j的最优解，转移是dp[i][j]=max(dp[i-1][j], dp[i-1][j-w]+v)。压缩成一维时，dp[j]要保留"上一轮"的值，所以更新dp[j]时必须用还没被当前物品改过的dp[j-w]，这要求j从大到小枚举；若从小到大，dp[j-w]已被当前物品更新，相当于同一物品用了两次，变成完全背包。

A错在"从小到大不漏解"——从小到大恰恰是用一次物品，漏解的是完全背包；C错在"方向无所谓"——一维DP方向决定是0/1还是完全背包，不是"无所谓"；D错在"初始为0方向无所谓"——初始值只影响边界，核心是转移时dp[j-w]是否被当前物品污染；最阴险的是"必须"二字，考生常以为"一维化后方向可任选"，其实倒序是唯一保证0/1性质的条件。

若把题目改成"完全背包一维优化"，内层j必须从小到大，答案变A；再问"二维dp能否用一维实现"，答案不变，但考点从"方向"变成"空间压缩"，这是六级常见变式。刷到类似题先问：是0/1还是完全？一维化后方向固定，别用直觉代结论。