0-1背包问题

0-1背包问题

蛮力枚举法

依次列出所有可能情况!!!

n表示有n个商品, C表示容量

image-20220511145827916

其中颜色相同的是需要重复计算的

带备忘的递归

为了解决这个问题->需要大量计算重复的过程,这个时候我们可以引进一个“备忘录”,如果遇到需要重复计算的式子的话,我们可以直接重备忘录中获取。

image-20220511153243852

伪代码的实现:

KnapsackMR(i, c)

1
输入:商品集合{1,...,i},背包容量c
1
输出:最大总价格P[i, c]
1
if(c < 0) then  容量为零 返回负无穷
1
return 负无穷
1
end
1
if i ≤ 0 then	如果商品的个数小于零的话,返回零
1
return 0
1
end
1
if P[i, c] ≠ NULL then  如果备忘录中有这个的话就不用计算 直接返回即可
1
return P[i, c]
1
end
1
P1 = KnapsackMR(i-1, c-vi)
1
P2 = KnapasckMR(i-1, c)
1
p[i, c] <= max{P1 + pi, P2}
1
return P[i, c]

计算顺序:

image-20220511154801451

为了能够不递推,直接求解P[i,c],这就需要我们事先把备忘录表,全部填写上去

p[i,c]确定的方法需要让p[i-1, c]和p[i-1,c-vi]+pi 相比较,选取其中较大的哪一个

image-20220511154927285

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
# 背包问题
# 第一个参数为商品数量
# 第二个参数为背包容量
# 第三个参数为价格表容量表
def memo_rec_matrix(num_commodity, size_knapsack, Price):
# 创建备忘录格式
memo = [ [ [] for i in range(size_knapsack+1)] for m in range(num_commodity+1)]

# 创建追踪表格 0 表示不选择该商品,1表示选择该商品
rec = [ [ [] for i in range(size_knapsack+1)] for m in range(num_commodity+1)]

# 初始化备忘录 和 追踪表格
for m in range(size_knapsack+1):
memo[0][m] = 0
rec[0][m] = 0


for m in range(num_commodity+1):
memo[m][0] = 0
rec[m][0] = 0

# 当我们商品数量为1 - num_commodity 的时候各种情况
for i in range(1, num_commodity+1):
# 当背包容量为1-size_knapsck的时候的各种情况
for m in range(1, size_knapsack+1):
# 如果背包容量小于第i个商品的体积的话,
# 就让memo数组对应的 商品数量i行 和 背包容量m列的位置 等于上一行的这一列的容量,
# 因为上一行这一列的容量是 这个容量是没有i个商品的容量最大值, 并且设置rec[i][m]这个位置为零
if m < Price[0][i-1]:
memo[i][m] = memo[i-1][m]
rec[i][m] = 0
# 如果背包容量大于第i个商品的体积的话,需要进行判断
else:
# 如果加上第i个商品之后的价值 小于没有加上该商品的价值的话,
# 那么就把该位置设置成没有加上第i个商品的时候价值
# 把rec该位置的坐标赋值为0 因为没有选择了该商品
if memo[i-1][m] > memo[i-1][m-Price[0][i-1]]+Price[1][i-1]:
memo[i][m] = memo[i-1][m]
rec[i][m] = 0
# 如果大于的话直接赋值就行
# 把rec该位置的坐标赋值为1 因为选择了该商品
else:
memo[i][m] = memo[i-1][m-Price[0][i-1]]+Price[1][i-1]
rec[i][m] = 1
return memo, rec


# 追踪数组
def track(rec, price):
rec_num_line = len(rec)-1
rec_num_column = len(rec[0])-1

while(True):
# 循环条件 商品数量为0
if rec_num_line == 0:
break
elif rec[rec_num_line][rec_num_column] == 0:
rec_num_line -= 1
else:
print(rec_num_line)
rec_num_line -= 1
rec_num_column -= price[0][rec_num_line]

price = [
[10,3,4,5,4], # 体积
[24,2,9,10,9] # 价格
]


# 商品数量
num_commodity = 5
# 背包容量
size_knapsack = 13


memo, rec = memo_rec_matrix(num_commodity,size_knapsack,price)