第10986题
判断0-1背包一维动态规划内层逆序循环改为正序遍历后是否仍能得到正确答案

以下代码实现了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()
A

正确

B

错误