单选题
适中
#16960
0/1 背包(每件物品最多选一次) 问题通常可用一维动态规划求解 ,核心代码如下 。遍历的方向无所谓 ,则下面说法正确的是( )。 def zero_one_k…
0/1 背包(每件物品最多选一次) 问题通常可用一维动态规划求解 ,核心代码如下 。遍历的方向无所谓 ,则下面说法正确的是( )。
答案与解析
正确答案:B
解析
动态规划数组 dp 表示容量为 j 时能获得的最大价值。每件物品仅可选择一次,更新状态时需确保当前物品的重量和价值不会基于本轮已更新的状态进行计算。内层循环遍历容量从 W 到 w,采用逆序确保每次状态转移依赖的是前一轮物品的 dp 值。若采用正序,则较小容量的状态先被更新,后续较大容量可能重复引用同一物品,导致物品被多次使用。逆序避免了当前轮次的状态覆盖对后续状态转移的影响。