01 背包问题
structure01 package
问题描述
一共有N件物品，第i（i从1开始）件物品的重量为w[i]，价值为v[i]。在总重量不超过背包承载上限W的情况下，求能够装入背包的最大价值是多少？
假设有一个 5 件物品，背包总重量 6，每一件的重量与价值如下
text
5 6
5 10 3 6 3 // 价值v
2 5 1 4 3 // 重量w横向背包可装总重量大小，纵向表示物品可选范围 0 ~ i, 单元格内为0 ~ i件物品的最大价值
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | |
|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 5 | 5 | 5 | 5 | 5 |
| 1 | 0 | 0 | 5 | 5 | 5 | 10 | 10 |
| 2 | 0 | 3 | 5 | 8 | 8 | 10 | 13 |
| 3 | 0 | 3 | 5 | 8 | 8 | 10 | 13 |
| 4 | 0 | 3 | 5 | 8 | 8 | 10 | 13 |
| 5 | 0 | 3 | 5 | 8 | 8 | 10 | 13 |
对于某一行某一列的物品 (i, j) 价值,最终判断是否可选的最大值 dp[i][j] = max(选择第 i 件物品的价值 , 不选第 i 件物品价值)
- 不选第 i 件物品价值: 第 i - 1 件物品的最大价值 dp[i - 1][j]
- 选择第 i 件物品的价值: 当前总重量 减去 第 i 件 物品后的重量可容纳的最大价值 dp[i - 1][j - w[i] ] + v[i]
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i] ] + v[i])
01 完全背包
n 个物品 变为 n 类物品，每一类物品可以选择多个
dp[i][j] = max(dp[i - 1][j], dp[i][j - w[i]] + v[i])