下面代码实现 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]
A：dp[w] = max(dp[w], dp[w - wt[i]] + val[i])
B：dp[w] = max(dp[w - 1], dp[w - wt[i]] + val[i])
C：dp[w] = dp[w] + val[i]
D：dp[w - wt[i]] = max(dp[w], val[i])
正确答案：A
答案解析
初始化 dp 数组表示容量从 0 到 W 的背包所能达到的最大价值，初始值为 0。外层循环遍历每个物品，内层循环从当前背包容量 W 递减到当前物品重量 wt[i]，确保每个物品只被考虑一次。状态转移时，对于每个容量 w，比较不选该物品时的价值 dp[w] 与选择该物品时的价值 dp[w - wt[i]] + val[i]，取较大者更新 dp[w]。递减遍历容量是为了避免同一物品被重复使用。最终 dp[W] 存储容量为 W 时的最大价值。
试卷来源：202606 CCF-GESP编程能力等级认证Python六级真题