0/1 背包使用一维数组优化时,容量从小到大枚举也能保证每件物品最多被选一次。
A:正确
B:错误
正确答案:错误
答案解析
在0/1背包问题中使用一维数组优化时,状态转移依赖于前一轮的值。为避免物品被重复选择,需确保当前容量状态更新时不覆盖后续未处理状态所需的历史值。若按容量从小到大枚举,当前状态会基于已被更新的较小容量状态计算,导致可能重复选取同一物品。逆序枚举容量可保证每次更新使用的是上一轮次的状态值,从而确保每件物品仅被考虑一次。顺序枚举破坏了状态间的依赖隔离,无法保证物品选择次数的唯一性。
试卷来源:202606 CCF-GESP编程能力等级认证Python七级真题