考察点:背包模型对比——物品能否重复选决定遍历方向,以及一维 DP 的降维原理。
核心答案:区别在于『同一物品能否重复装入』,这直接决定了状态压缩时容量维度的遍历方向。
要点(转移区别):
dp[j] = max(dp[j], dp[j-w] + v),其中 dp[j] 用到的 dp[j-w] 必须是『上一轮(不含当前物品)』的值。dp[j] = max(dp[j], dp[j-w] + v),但允许重复用当前物品,所以要基于『本轮已更新』的 dp[j-w]。要点(为什么遍历方向不同):
dp[j] 时 dp[j-w] 还是旧值(没被当前物品覆盖);完全背包顺序遍历 j(从 w 到 W),让 dp[j-w] 已是本轮更新过的,从而可重复选。题目与答案就在本页;收藏、批注和错题重练在应用内