判断题 偏易
#16719

以下代码实现了0 -1背包问题的一维动态规划解法,内层循环采用经典的逆序遍历方式。若将内层循环改为正序遍历(即for j in range(w[i], W +…

以下代码实现了0 -1背包问题的一维动态规划解法,内层循环采用经典的逆序遍历方式。若将内层循环改为正序遍历(即for j in range(w[i], W + 1):),仍能得到正确答案。

def knapsack_01():
    W = 5
    w = [2, 3, 4]
    v = [10, 1, 1]
    n = 3
    dp = [0] * (W + 1)

    for i in range(n):
        for j in range(W, w[i] - 1, -1):
            dp[j] = max(dp[j], dp[j - w[i]] + v[i])

    print(dp[W])

knapsack_01()


未登录也能判分,登录后才会记录
答案与解析
正确答案:错
解析
分析二维状态转移方程在压缩为一维时的状态更新顺序。逆序遍历确保每次更新依赖的是上一轮的状态值,避免同一物品被重复选择。正序遍历会使用本轮已更新的状态值,导致状态依赖发生改变。当物品重量与价值关系满足特定条件时,正序可能恰好得到相同结果。需验证每轮状态更新过程中对dp[j]的访问是否覆盖了所有必要情况。比较两种遍历方式下每个j位置的来源状态是否等价。检查物品不可拆分的前提下,容量递增或递减更新对状态覆盖的影响。