【LeetCode & 剑指offer 刷题笔记】目录（持续更新中...）
背包问题总结
背包问题 背包问题 (Knapsack problem x ) 有很多种版本，常见的是以下三种：- 0-1 背包问题 (0-1 knapsack problem)：每种物品只有一个
- 完全背包问题 (UKP, unbounded knapsack problem)：每种物品都有无限个可用
- 多重背包问题 (BKP, bounded knapsack problem)：第 i 种物品有 n[i] 个可用
0-1 背包问题0-1背包中一种物体只有一个，放入数量为0或者1定义状态 dp[i][j]，表示“把前 i 种物品装进重量限制为 j 的背包可以获得的最大价值”v[i]表示物品i的价值，w[i]表示物品i的重量，j为背包的重量限制0/1背包问题状态转移方程便是： dp[i][j] = max{dp[i − 1][j], dp[i − 1][j − w[i]] + v[i]} 两项分别代表物品i不选择或者选择的情况 (减去的代表选择的)时间复杂度是O(nb),空间也是O(nb)，假设有n种物品，重量限制为b 可以简化为: d[j]=max{d[j],d[j-w[i]]+v[i]};注意：遍历j时务必从右到左，因为d[j]只依赖于上一阶段的结果，从右到左避免覆盖上阶段有用结果 完全背包问题完全背包中一种物体可以有多个，可以放满背包为止完全背包问题状态转移方程是： dp[i][j] = max{dp[i − 1][j], dp[i][j − w[i]] + v[i]}两项分别代表物品i不选择或者选择，由于对物品i没有限制，故后一项为dp[i]而非上面的dp[i-1] 或用以下递推式（上面的效率要高一点）：dp[i][j] = max( dp[i-1][j-k*w[i]] + k*v[i] ), k为选择物品的个数， k=0,1,2...j/w[i] (0 ≤ k ∗ w[i] ≤ j)基于前i-1个物品，在选择不同个数的物品i的方案中选择最大的那个（和问题coin change 比较相似） 可以简化为： d[j] = max{d[j], d[j-k*w[i]] + k*v[i]}注意：遍历j时务必从右到左，原因同上 多重背包问题多重背包中一种物体可以有多个，个数有人为限定（也不能超过背包容量）多重背包问题状态转移方程是：dp[i][j] = max( dp[i−1][j−k∗w[i]] + k∗v[i] ) 0 ≤ k ≤ n[i],0 ≤ k ∗ w[i] ≤ jn[i]为物品i限制的个数基于前i-1个物品，在选择不同个数的物品i的方案中选择最大的那个 可以简化为： d[j] = max{d[j], d[j-k*w[i]] + k*v[i]}注意：遍历j时务必从右到左，原因同上 参考：【动态规划】背包问题（一） 01背包 完全背包 多重背包 - A.S.KirigiriKyouko - 博客园背包问题总结
posted @ 2019-01-06 16:56 wikiwen 阅读(...) 评论(...) 编辑 收藏