https://www.bilibili.com/video/BV1mA411n7rR?spm_id_from=333.880.my_history.page.click
01 背包
问题
最基本的背包问题就是01背包问题（01 knapsack problem）：一共有 n 件物品，第 i（i从1开始）件物品的体积 v[i]，价值为 w[i] 。 在总体积不超过背包承载上限 m 的情况下，能够装入背包的最大价值是多少？
定义
使用
dp[i][j]表示将 前 i 件物品装进体积为 j 的背包可以获得的最大价值, 0<=i<=N, 0<=j<= m
再来分析整个运转流程：
如图所示，描述略。见视频吧。
因此得到的朴素版本的状态转移方程是：
经过滚动数组优化后的 01背包问题转移方程代码示例：
dp[0,...,m] = 0
for (int i = 1; i < n; i++) {
// 必须逆向枚举!!!
for (int j = m; j >= v[i]; j--) {
dp[j] = Max( dp[j] , dp[j - v[i]] + w[i] );
}
}
- 时间：O(n*m)，即取决于物品数量和背包体积
- 空间：O(m)
完全背包
问题
完全背包（unbounded knapsack problem）与01背包不同就是每种物品可以有无限多个：一共有 N 种物品，每种物品有无限多个，第 i（i从1开始）种物品的体积为 v[i] ，价值为 w[i]。在总重量不超过背包承载上限 m 的情况下，能够装入背包的最大价值是多少？
定义
使用
dp[i][j]表示将 前 i 件物品装进体积为 j 的背包可以获得的最大价值, 0<=i<=N, 0<=j<= m
因此得到的状态转移方程是：
dp[i][j] = max(dp[i−1][j], dp[i][j−v[i] ] + w[i] ) // j >= w[i]这个状态转移方程与01背包问题唯一不同就是 max 第二项 不是 dp[i-1] 而是 dp[i]
最终经过恒等变形的代码如下：
//完全背包
dp[0,...,m] = 0
public void fun02() {
for (int i = 1; i <= n; i++) {
// 必须正向枚举!!!
for (int j = v[i]; j <= m; j++) {
dp[j] = Max(dp[j], dp[j - v[i]] + w[i]);
}
}
}
- 时间：O(n*m)，即取决于物品数量和背包体积
- 空间：O(m)
其他
