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)