共计 1093 个字符，预计需要花费 3 分钟才能阅读完成。
最近在温习算法常识写下这篇文章帮忙本人了解记忆
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]正文完