[type]动态规划-背包问题

[Alice52]

背包问题

01背包: core

1. 每件物品只能用一次
2. dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])
   • dp[i - 1][j - weight[i]]: j-weight[i]{等下要装入 i[必须能装i]} 容量的背包装入 0~i-1 的最大值,
   • dp[i][j]: 0~i的物品装入 j 容量的背包的最大值
3. 优化滚动数组: dp[j] = max(dp[j], dp[j - weight[i]] + value[i])
   • 公式推导: dp[j] 的针对i的最大值只有i选与不选
     • 选 i 则 dp[j] = dp[j - weight[i]] + value[i]
     • 选 i 则 dp[j] = dp[j] 没有动背包所以最大值没变
   • 容量 j 的背包, 0~i内的物品最大价值
   • 物品for + 背包 for{倒序}

完全背包

1. 完全背包的物品数量是无限的

多重背包