理论基础
<aside>
💡 经典题目：
一个容量为4的背包,一共有3个物品 重量weight = [1,3,4], 价值 value = [10,25,30]
背包如何背才能获得最大的价值
</aside>
二维数组
- dp[i][j] 含义 从[0-i]的物品里任意取 放到 背包容量为j的背包里面 背包所背的最大价值
- 递推公式 dp[i][j] = max(dp[i-1][j],dp[i-1][j-weight[i]] + value[i])
- 先遍历物品 后遍历背包
|
背包容量 |
dp[i][j] |
0 |
1 |
2 |
3 |
4 |
| 10 |
1 |
物品0 |
0 |
10 |
10 |
10 |
10 |
| 25 |
3 |
物品1 |
0 |
10 |
10 |
25 |
35 |
| 30 |
4 |
物品2 |
0 |
10 |
10 |
25 |
35 |
|
背包容量 |
dp[i][j] |
0 |
1 |
2 |
3 |
4 |
| 10 |
1 |
物品0 |
0 |
10 |
10 |
10 |
10 |
| 25 |
3 |
物品1 |
0 |
10 |
10 |
25 |
35 |
| 30 |
4 |
物品2 |
0 |
10 |
10 |
25 |
35 |
二维数组 如何遍历没有变化 背包和物品都是 从前往后遍历
def packet(weight,value,bag_weight):
# 定义dp数组
dp = [[0 for _ in range(bag_weight+1)] for _ in range(len(weight))]
# 初始化 dp数组
for j in range(len(dp[0])):
# if dp[0][j] >= weight[0]: 错误 做法 ❎
if j >= weight[0]: ✅
dp[0][j] = value[0]
# 先遍历物品
for i in range(1,len(weight)):
# 遍历背包
for j in range(weight[i],bag_weight+1):
# 递推公式
dp[i][j] = max(dp[i-1][j],dp[i-1][j-weight[i]] + value[i])
return dp[-1][-1]
滚动数组 （一维）
- dp[j] 含义 背包为j 的容量时 所能背的最大价值 （将上层的数组复制下来）
- 递推公式 dp[j] = max(dp[j],dp[j-weight[i]] + value[i])
- 先遍历物品 在遍历背包 前 → 后 遍历背包 ❎ 物品被重复使用
|
背包容量 |
dp[j] |
0 |
1 |
2 |
3 |
4 |
| 10 |
1 |
物品0 |
0 |
10 |
20 |
30 |
40 |
| 25 |
3 |
物品1 |
0 |
10 |
20 |
30 |
40 |
| 30 |
4 |
物品2 |
0 |
10 |
20 |
30 |
40 |
|
背包容量 |
dp[j] |
0 |
1 |
2 |
3 |
4 |
| 10 |
1 |
物品0 |
0 |
10 |
10 |
10 |
10 |
| 25 |
3 |
物品1 |
0 |
10 |
10 |
25 |
35 |
| 30 |
4 |
物品2 |
0 |
10 |
10 |
25 |
35 |
def packet_(weight,value,bag_weight):
# 定义 dp数组
dp =[0 for _ in range(bag_weight+1)]
# 初始化 dp数组 初始为0 不用操作
# 先遍历物品
for i in range(1,len(weight)):
# 遍历背包 从后 往前
for j in range(bag_weight,weight[i]-1,-1):
dp[j] = max(dp[j],dp[j-weight[i]] + value[i])
return dp[-1]