A18745. $下面代码实现 0/1 背包的一维动态规划。第 i 个物品重量为 wt[i] ，价值为 val[i] ，背包容量为 W 。横线处应填写（）。def knapsack(W, wt, val): n = len(wt) dp = [0] * (W + 1) for i in range(n): for w in range(W, wt[i] - 1, -1): ___________________\dots$

单选题困难

知识点

动态规划一维数组优化 0/1背包

题目描述

下面代码实现 0/1 背包的一维动态规划。第 i 个物品重量为 wt[i] ，价值为 val[i] ，背包容量为 W 。横线处应填写（ ）。 def knapsack(W, wt, val): n = len(wt) dp = [0] * (W + 1) for i in range(n): for w in range(W, wt[i] - 1, -1): __________________________ return dp[W]

dp[w] = max(dp[w], dp[w - wt[i]] + val[i])

dp[w] = max(dp[w - 1], dp[w - wt[i]] + val[i])

dp[w] = dp[w] + val[i]

dp[w - wt[i]] = max(dp[w], val[i])

上一题下一题