下面代码是一维数组优化 0/1 背包的核心片段,其中 w[i] 表示第 i 件物品的重量,v[i] 表示第 i 件物品的价值。横线处应填入( )。
for (int i = 1; i <= n; i++) {
for (int c = W; c >= w[i]; c--) {
__________;
}
}
- A. dp[c] = max(dp[c], dp[c + w[i]] + v[i])
- B. dp[c] = min(dp[c], dp[c - w[i]] + v[i])
- C. dp[c] = dp[c - w[i]] + v[i]
- D. dp[c] = max(dp[c], dp[c - w[i]] + v[i])
正确答案：D