最近在温习算法常识写下这篇文章帮忙本人了解记忆
01 背包问题
01背包问题的指标是在固定的容量限度内，达到最大的物品价值
01对含意:无奈宰割物品
01背包问题通常有暴力回溯法和动静布局两种形式来解决
Brute Force
回溯法查看所有组合 工夫复杂度为指数级
很容易工夫就爆表，这里就不看了
动静布局
动静布局的外围在于寻找子问题，在这个题中咱们首先去寻找子问题
寻找子问题
假如背包最大分量为5
物品信息如下
| 分量 | 价值 | |
|---|---|---|
| 物品1 | 4 | 7 |
| 物品2 | 3 | 5 |
| 物品3 | 5 | 6 |
| 物品4 | 3 | 3 |
| 物品5 | 2 | 8 |
dp表的每一个地位存储的是这么大的背包，最大收益是多少
咱们首先思考，如果只有物品1， 如果装不下，收益就是0
如果咱们的背包能够装下，那么最大收益就是7，咱们更新第一行
| 0 | 1 | 2 | 3 | 4 | 5 | |
|---|---|---|---|---|---|---|
| 物品1 | 0 | 0 | 0 | 0 | 7 | 7 |
| 物品2 | ||||||
| 物品3 | ||||||
| 物品4 | ||||||
| 物品5 |
通过解决子问题取得到全局问题的解
当初思考物品2，如果装不下，收益就是上一行雷同地位的后果
如果能装下：判断上一行雷同地位的后果 此物品价值加上上一行去掉此物品分量后的分量最多能装的价值
由此咱们取得状态转移方程
dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]]+values[i])| 0 | 1 | 2 | 3 | 4 | 5 | |
|---|---|---|---|---|---|---|
| 物品1 | 0 | 0 （4 - weight of item 2） | 0 | 0 | 7 | 7 |
| 物品2 | 0 | 0 | 0 | 5 | max(7, (5 + 0)) | |
| 物品3 | ||||||
| 物品4 | ||||||
| 物品5 |
一直迭代
| 0 | 1 | 2 | 3 | 4 | 5 | |
|---|---|---|---|---|---|---|
| 物品1 | 0 | 0 | 0 | 0 | 7 | 7 |
| 物品2 | 0 | 0 | 0 | 5 | 7 | 7 |
| 物品3 | 0 | 0 | 0 | 5 | 7 | 7 |
| 物品4 | 0 | 0 | 0 | 5 | 7 | 7 |
| 物品5 | 0 | 0 | 8 | 8 | 8 | 13 |
最初后果为13
残缺Python代码如下
## 代码中的类名、办法名、参数名曾经指定，请勿批改，间接返回办法规定的值即可## 计算01背包问题的后果# @param V int整型 背包的体积# @param n int整型 物品的个数# @param vw int整型二维数组 第一维度为n,第二维度为2的二维数组,vw[i][0],vw[i][1]别离形容i+1个物品的vi,wi# @return int整型#class Solution: def knapsack(self, V: int, n: int, vw: List[List[int]]) -> int: # write code here dp = [[0] * (V + 1) for _ in range(n)] for i in range(V + 1): if i >= vw[0][0]: dp[0][i] = vw[0][1] for i in range(1, n): for j in range(V + 1): if j < vw[i][0]: dp[i][j] = dp[i-1][j] else: dp[i][j] = max(dp[i-1][j], dp[i-1][j-vw[i][0]]+vw[i][1]) return dp[n-1][V]