使用启发式算法解决多背包问题
mufiye 内核新手
  2021-05-28 22:43:28 2021-05-28 22:43      4.4k 字  22 分钟  

使用启发式算法解决多背包问题

1. 问题介绍

要讲多背包问题，我们先来讲一讲单背包问题。单背包问题是关于如何将将不同的物品放入到一个背包中。这些物品有重量和价值这两个属性，并且背包有容量限制这一个属性。这个单背包问题的目标就是最大化放入背包中物品的总价值同时这些物品的重量之和不能超过背包的容量限制。而多背包问题是单背包问题的拓展，该问题考虑多个背包的情况而不是一个背包的情况。但是它可以使用类似解决单背包问题的策略去解决多背包问题。多背包问题的目标是最大化所有背包中所含物品的总价值，同时每一个背包中的物品质量之和不能超过这个背包的容量限制。

2. 算法

2.1 贪心算法（greedy algorithm）

为了解决多背包问题，我们可以仅仅考虑当前要将什么物品放入背包中。使用贪心算法，我们根据物品的性价比(价值/重量)对物品进行排序，在序列前面的物品优先考虑放入某个背包中。此时我们已经决策了关于将什么物品放入背包中，但是我们仍未决策将物品放入哪个背包中，此时有三种策略，分别是best fit，worst fit和first fit（没错，就是操作系统中会学到的那三个概念）。同时如果没有哪个背包能够容纳当前的物品，那么说明该物品无法放入背包中，此时我们考虑序列中的下一个物品，直至遍历完整个序列。

2.2 邻居搜索（neighborhood search）

邻居搜索也是一种启发式算法。它将一个解决多背包问题的方案作为一个元素，之后以某个方案作为起点，搜索该方案的邻居中的更优方案（即背包中的物品价值总和更大），直至当前方案的邻居中没有更优的解决方案则认为当前的解决方案为最优的解决方案。

该算法很重要的一个部分就是如何定义一个解决方案的邻居，在该问题中，我定义了三种邻居：第一种邻居是将一个物品放入一个背包中；第二种邻居是取出一个背包中的物品并将另一个物品放入其中一个背包；第三种邻居相对比较复杂，可以称之为旋转操作，该操作会涉及三个物品，我假设他们分别为A，B，C，物品A在背包m中，物品B在背包n中同时物品C不在任何一个背包中。我们将物品A从背包m中取出，将物品B放入背包m中并且将物品C放入背包n中。通过定义的这三种邻居，我们可以搜索某个方案的邻居并找到局部最优解。

2.3 禁忌搜索（tabu-search）

禁忌搜索也是一种启发式算法，它是对邻居搜索的一种改良。在禁忌搜索中，我们也需要去寻找一个解决方案的邻居解法，但是该算法改变了终止搜索的方式以及记录最优解的方式。在该算法中，我们定义一个禁忌列表来记录之前的解法，一个数值来记录最大迭代次数，一个变量来记录当前的最优解。在禁忌搜索中，也是以某个解决方案为起点，搜索该方案A的邻居，找到所有邻居中不被包含在禁忌列表的方案中的最优解B（不需要该解法优于方案A），同时将方案A放入禁忌列表中（禁忌列表其实是一个队列，如果超过列表的容量，就将队列首部的方案移出队列），并且比较方案B是否优于当前记录的最优解法，如果优于，则更新。此时已方案B为新的起点，重复上述过程，直到迭代次数达到规定的上限或者邻居解法中不存在不在禁忌列表中的解法，退出循环。

3. 代码实现

3.1 伪代码

multipac-greedy

multipac-neighbor

multipac-tabu

3.2 python代码实现

我使用python实现这三种算法，为了表达物品和背包，我定义了物品类和背包类。物品类有重量（weight）和价值（value）这两个属性，背包类有当前剩余容量和初始容量这两个属性。在贪心算法中，我模拟模拟物品的放置流程通过改变背包的剩余容量属性（capacity）。但是在邻居搜索和禁忌搜索算法中，我使用矩阵去记录解决方案。如果矩阵中的第i行和第j列等于1，那么代表第i个物品在第j个背包中。为了判断某个背包是否能够包含某个物品，我定义了judgeWeight函数。为了计算当前所有在背包中的物品的总价值，我定义了calValue函数。同时在禁忌搜索中，我定义了check_tabu函数去判断某个解决方案是否在禁忌列表中。所有的函数都是对矩阵进行操作。在禁忌搜索中，我定义了tabu_length变量来控制禁忌列表的长度，这个变量是算法的一个输入。

接下来，我按顺序实现了三种算法。我使用相同的测试用例来评价这三种算法。贪心算法总是得到总价值为13的解决方案，邻居搜索算法搜索到的解决方案总价值为14，禁忌搜索最终能够找到总价值为15的解决方案。

1
2
3
4
5
6
7
8
9
10
11
12
13
import numpy as np

class goods:
    def __init__(self,weight,value):
        self.weight=weight
        self.value=value

class bags:
    def __init__(self,original_capacity):
        self.original_capacity=original_capacity
        self.capacity=self.original_capacity
    def clearAll(self):
        self.capacity=self.original_capacity

贪心算法：

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
def multiple_knapsack_greedy(bags_set=[], goods_set=[]):
    goods_set2=goods_set.copy()   
    goods_set2.sort(key=lambda x: x.value / x.weight, reverse=True)
    result = np.zeros(shape=(len(goods_set),len(bags_set)))
    total_value = 0
    for i in range(len(goods_set2)):
        good=goods_set2[i]
        res=[] #record the index of bag which can contain the good
        for j in range(len(bags_set)):
            if good.weight<=bags_set[j].capacity:
                res.append(j)
        if not res==[]:
            min=bags_set[res[0]].capacity
            minIndex=res[0]
            for k in res[1:]:
                if bags_set[k].capacity<min:#best fit
                    min=bags_set[k].capacity
                    minIndex=k
            total_value+=good.value
            goodIndex=goods_set.index(good)
            result[goodIndex][minIndex]=1
            print("put good{} into bag{}".format(goodIndex+1,minIndex+1))
            bags_set[minIndex].capacity-=good.weight
    for bag in bags_set:
         bag.clearAll()
    print("------------------------")
    print("The final result is:")
    print("the finial total value is: {}".format(total_value))
    print("the finial puttting matrix is:")
    print(result)
    print()
    for i in range(len(bags_set)):
        print("bag{} contains:".format(i+1))
        for j in range(len(goods_set)):
            if result[j][i]==1:
                print("  good{} has weight of {} and value of {}".format(j+1,goods_set[j].weight,goods_set[j].value))
    print("The bags' total value is {}.".format(total_value))
    return result,total_value

邻居搜索：

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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
def judgeWeight(result,bagsWeightList,goodsWeightMat):
     sumWeightMat=np.multiply(result,goodsWeightMat)
     sumWeightVec=np.sum(sumWeightMat,axis=0)
     return (sumWeightVec<=bagsWeightList).all()

def calValue(result,goodsValueMat):
     sumValueMat=np.multiply(result,goodsValueMat)
     return np.sum(sumValueMat)

#neighborhood search
def multiple_knapsack_neighbor(bags_set=[], goods_set=[]):
    bagsWeightList=[bag.original_capacity  for bag in bags_set]
    bagsWeightList=np.array(bagsWeightList)
    goodsWeightMat=np.zeros(shape=(len(goods_set),len(bags_set)))
    goodsValueMat=np.zeros(shape=(len(goods_set),len(bags_set)))
    for i in range(len(goods_set)):
         for j in range(len(bags_set)):
             goodsWeightMat[i][j]=goods_set[i].weight
    for i in range(len(goods_set)):
         for j in range(len(bags_set)):
             goodsValueMat[i][j]=goods_set[i].value
            
    current_result,current_total_value = np.zeros(shape=(len(goods_set),len(bags_set))),0
    iterateNum=1
    isEnd=False
    print("--------------------------------")
    print("the initial total value is: {}".format(current_total_value))
    print("the initial putting matrix is:")
    print(current_result)
    while not isEnd:
       next_result,next_total_value  = np.zeros(shape=(len(goods_set),len(bags_set))),0
       allZeroIndexList,haveOneIndexList=[],[]
       if len(haveOneIndexList)==len(goods_set):
             break
       for i in range(len(goods_set)):
            if np.sum(current_result[i:i+1,::],axis=1)[0]==0:
                allZeroIndexList.append(i)
            else:
                haveOneIndexList.append(i)
       if len(haveOneIndexList)==0:
            #sameBlock1
            for i in allZeroIndexList:
                for j in range(len(bags_set)):
                    mid_result=current_result.copy()
                    mid_result[i][j]=1
                    if judgeWeight(mid_result,bagsWeightList,goodsWeightMat):
                        mid_total_value=calValue(mid_result,goodsValueMat)
                        if mid_total_value>next_total_value:
                             next_result = mid_result
                             next_total_value = mid_total_value
                        break
       elif len(haveOneIndexList)==1:
            #sameBlock1
            for i in allZeroIndexList:
                for j in range(len(bags_set)):
                    mid_result=current_result.copy()
                    mid_result[i][j]=1
                    if judgeWeight(mid_result,bagsWeightList,goodsWeightMat):
                        mid_total_value=calValue(mid_result,goodsValueMat)
                        if mid_total_value>next_total_value:
                             next_result = mid_result
                             next_total_value = mid_total_value
                        break
            #sameBlock2           
            for i in allZeroIndexList:
                for j in haveOneIndexList:
                    mid_result=current_result.copy()
                    mid_result[j,::]=current_result[i,::]
                    mid_result[i,::]=current_result[j,::]
                    if judgeWeight(mid_result,bagsWeightList,goodsWeightMat): 
                        mid_total_value=calValue(mid_result,goodsValueMat)
                        if mid_total_value>next_total_value:
                            next_result = mid_result
                            next_total_value = mid_total_value
       else:
            #sameBlock1
            for i in allZeroIndexList:
                for j in range(len(bags_set)):
                    mid_result=current_result.copy()
                    mid_result[i][j]=1
                    if judgeWeight(mid_result,bagsWeightList,goodsWeightMat):
                        mid_total_value=calValue(mid_result,goodsValueMat)
                        if mid_total_value>next_total_value:
                             next_result = mid_result
                             next_total_value = mid_total_value
                        break
            #sameBlock2            
            for i in allZeroIndexList:
                for j in haveOneIndexList:
                    mid_result=current_result.copy()
                    mid_result[j,::]=current_result[i,::]
                    mid_result[i,::]=current_result[j,::]
                    if judgeWeight(mid_result,bagsWeightList,goodsWeightMat): 
                        mid_total_value=calValue(mid_result,goodsValueMat)
                        if mid_total_value>next_total_value:
                            next_result = mid_result
                            next_total_value = mid_total_value
            #rotate              
            for i in  range(len(haveOneIndexList)):
                for j in range(i,len(haveOneIndexList)):
                    index1=haveOneIndexList[i]
                    index2=haveOneIndexList[j]
                    for k in allZeroIndexList:
                        for case in range(2):
                            if(case==1):
                                index1,index2=index2,index1
                            mid_result=current_result.copy()
                            mid_result[k,::]=current_result[index1,::]
                            mid_result[index1,::]=current_result[index2,::]
                            mid_result[index2,::]=current_result[k,::]
                            if judgeWeight(mid_result,bagsWeightList,goodsWeightMat): 
                                mid_total_value=calValue(mid_result,goodsValueMat)
                                if mid_total_value>next_total_value:
                                     next_result = mid_result
                                     next_total_value = mid_total_value
       if next_total_value > current_total_value:
            current_total_value=next_total_value
            current_result=next_result
            print("--------------------------------")
            print("iteration {}:".format(iterateNum))
            print("the current total value is: {}".format(current_total_value))
            print("the current putting matrix is:")
            print(current_result)
       else:
            isEnd=True
       iterateNum+=1
    print("--------------------------------")
    print("--------------------------------")
    print("--------------------------------")
    print("The final result is:")
    print("the finial total value is: {}".format(current_total_value))
    print("the finial puttting matrix is:")
    print(current_result)
    print()
    for i in range(len(bags_set)):
        print("bag{} contains:".format(i+1))
        for j in range(len(goods_set)):
            if current_result[j][i]==1:
                print("  good{} has weight of {} and value of {}".format(j+1,goods_set[j].weight,goods_set[j].value))
    return current_result,current_total_value

禁忌搜索：

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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
def check_tabu(tabu_list,mid_result):
    if len(tabu_list)<1:
        return False
    for i in range(len(tabu_list)):
        if (tabu_list[i][0]==mid_result).all():
            return True
    return False
def multiple_knapsack_tabu(bags_set=[], goods_set=[],tabu_length=1):#tabu search
    bagsWeightList=[bag.original_capacity  for bag in bags_set]
    bagsWeightList=np.array(bagsWeightList)
    goodsWeightMat=np.zeros(shape=(len(goods_set),len(bags_set)))
    goodsValueMat=np.zeros(shape=(len(goods_set),len(bags_set)))
    for i in range(len(goods_set)):
         for j in range(len(bags_set)):
             goodsWeightMat[i][j]=goods_set[i].weight
    for i in range(len(goods_set)):
         for j in range(len(bags_set)):
             goodsValueMat[i][j]=goods_set[i].value
            
    all_zero_result = np.zeros(shape=(len(goods_set),len(bags_set)))
    current_result,current_total_value  = np.zeros(shape=(len(goods_set),len(bags_set))),0
    best_result,best_total_value =current_result.copy(),current_total_value
    iterateNum,isEnd,tabu_list=1,False,[]
    if tabu_length>=1:
        tabu_list.append((current_result.copy(),current_total_value))
    print("--------------------------------")
    print("the initial total value is: {}".format(current_total_value))
    print("the initial putting matrix is:")
    print(current_result)
    while not isEnd and iterateNum<15:
       next_result,next_total_value  = np.zeros(shape=(len(goods_set),len(bags_set))),0
       allZeroIndexList,haveOneIndexList=[],[]
       if len(haveOneIndexList)==len(goods_set):
             break
       for i in range(len(goods_set)):
            if np.sum(current_result[i:i+1,::],axis=1)[0]==0:
                allZeroIndexList.append(i)
            else:
                haveOneIndexList.append(i)
       if len(haveOneIndexList)==0:
            #sameBlock1
            for i in allZeroIndexList:
                for j in range(len(bags_set)):
                    mid_result=current_result.copy()
                    mid_result[i][j]=1
                    if judgeWeight(mid_result,bagsWeightList,goodsWeightMat):
                        mid_total_value=calValue(mid_result,goodsValueMat)
                        if mid_total_value>next_total_value and not check_tabu(tabu_list,mid_result):
                             next_result = mid_result
                             next_total_value = mid_total_value
                        break
       elif len(haveOneIndexList)==1:
            #sameBlock1
            for i in allZeroIndexList:
                for j in range(len(bags_set)):
                    mid_result=current_result.copy()
                    mid_result[i][j]=1
                    if judgeWeight(mid_result,bagsWeightList,goodsWeightMat):
                        mid_total_value=calValue(mid_result,goodsValueMat)
                        if mid_total_value>next_total_value and not check_tabu(tabu_list,mid_result):
                             next_result = mid_result
                             next_total_value = mid_total_value
                        break
            #sameBlock2            
            for i in allZeroIndexList:
                for j in haveOneIndexList:
                    mid_result=current_result.copy()
                    mid_result[j,::]=current_result[i,::]
                    mid_result[i,::]=current_result[j,::]
                    if judgeWeight(mid_result,bagsWeightList,goodsWeightMat): 
                        mid_total_value=calValue(mid_result,goodsValueMat)
                        if mid_total_value>next_total_value and not check_tabu(tabu_list,mid_result):
                            next_result = mid_result
                            next_total_value = mid_total_value
       else:
            #sameBlock1
            for i in allZeroIndexList:
                for j in range(len(bags_set)):
                    mid_result=current_result.copy()
                    mid_result[i][j]=1
                    if judgeWeight(mid_result,bagsWeightList,goodsWeightMat):
                        mid_total_value=calValue(mid_result,goodsValueMat)
                        if mid_total_value>next_total_value and not check_tabu(tabu_list,mid_result):
                             next_result = mid_result
                             next_total_value = mid_total_value
                        break
            #sameBlock2            
            for i in allZeroIndexList:
                for j in haveOneIndexList:
                    mid_result=current_result.copy()
                    mid_result[j,::]=current_result[i,::]
                    mid_result[i,::]=current_result[j,::]
                    if judgeWeight(mid_result,bagsWeightList,goodsWeightMat): 
                        mid_total_value=calValue(mid_result,goodsValueMat)
                        if mid_total_value>next_total_value and not check_tabu(tabu_list,mid_result):
                            next_result = mid_result
                            next_total_value = mid_total_value
            #rotate            
            for i in  range(len(haveOneIndexList)):
                for j in range(i,len(haveOneIndexList)):
                    index1=haveOneIndexList[i]
                    index2=haveOneIndexList[j]
                    for k in allZeroIndexList:
                        for case in range(2):
                            if(case==1):
                                index1,index2=index2,index1
                            mid_result=current_result.copy()
                            mid_result[k,::]=current_result[index1,::]
                            mid_result[index1,::]=current_result[index2,::]
                            mid_result[index2,::]=current_result[k,::]
                            if judgeWeight(mid_result,bagsWeightList,goodsWeightMat): 
                                mid_total_value=calValue(mid_result,goodsValueMat)
                                if mid_total_value>next_total_value and not check_tabu(tabu_list,mid_result):
                                     next_result = mid_result
                                     next_total_value = mid_total_value
       
       if (next_result == all_zero_result).all():
            isEnd = True
       else:
           if tabu_length>=1:
               if len(tabu_list)>=tabu_length:
                   tabu_list.remove(tabu_list[0])
                   tabu_list.append((current_result,current_total_value))
               else:
                   tabu_list.append((current_result,current_total_value))

           current_total_value=next_total_value
           current_result=next_result
            
           if current_total_value>best_total_value:
                best_result=current_result.copy()
                best_total_value=current_total_value
           print("--------------------------------")
           print("iteration {}:".format(iterateNum))
           print("the current total value is: {}".format(current_total_value))
           print("the current putting matrix is:")
           print(current_result)
           iterateNum+=1
            
    print("--------------------------------")
    print("--------------------------------")
    print("--------------------------------")
    print("The final result is:")
    print("the finial total value is: {}".format(best_total_value))
    print("the finial puttting matrix is:")
    print(best_result)
    print()
    for i in range(len(bags_set)):
        print("bag{} contains:".format(i+1))
        for j in range(len(goods_set)):
            if best_result[j][i]==1:
                print("  good{} has weight of {} and value of {}".format(j+1,goods_set[j].weight,goods_set[j].value))
    return best_result,best_total_value

贪心搜索测试：

1
2
3
goods_set=[goods(4,3),goods(5,4),goods(6,5),goods(7,5),goods(1,2),goods(3,3)]
bags_set=[bags(10),bags(2),bags(1),bags(6)]
result,total_value=multiple_knapsack_greedy(bags_set,goods_set)

贪心搜索测试结果：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
put good5 into bag3
put good6 into bag4
put good3 into bag1
put good1 into bag1
------------------------
The final result is:
the finial total value is: 13
the finial puttting matrix is:
[[1. 0. 0. 0.]
 [0. 0. 0. 0.]
 [1. 0. 0. 0.]
 [0. 0. 0. 0.]
 [0. 0. 1. 0.]
 [0. 0. 0. 1.]]

bag1 contains:
  good1 has weight of 4 and value of 3
  good3 has weight of 6 and value of 5
bag2 contains:
bag3 contains:
  good5 has weight of 1 and value of 2
bag4 contains:
  good6 has weight of 3 and value of 3
The bags' total value is 13.

邻居搜索测试：

1
2
3
goods_set=[goods(4,3),goods(5,4),goods(6,5),goods(7,5),goods(1,2),goods(3,3)]
bags_set=[bags(10),bags(2),bags(1),bags(6)]
result,total_value=multiple_knapsack_neighbor(bags_set,goods_set)

邻居搜索测试结果：

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
--------------------------------
the initial total value is: 0
the initial putting matrix is:
[[0. 0. 0. 0.]
 [0. 0. 0. 0.]
 [0. 0. 0. 0.]
 [0. 0. 0. 0.]
 [0. 0. 0. 0.]
 [0. 0. 0. 0.]]
--------------------------------
iteration 1:
the current total value is: 5.0
the current putting matrix is:
[[0. 0. 0. 0.]
 [0. 0. 0. 0.]
 [1. 0. 0. 0.]
 [0. 0. 0. 0.]
 [0. 0. 0. 0.]
 [0. 0. 0. 0.]]
--------------------------------
iteration 2:
the current total value is: 9.0
the current putting matrix is:
[[0. 0. 0. 0.]
 [0. 0. 0. 1.]
 [1. 0. 0. 0.]
 [0. 0. 0. 0.]
 [0. 0. 0. 0.]
 [0. 0. 0. 0.]]
--------------------------------
iteration 3:
the current total value is: 12.0
the current putting matrix is:
[[1. 0. 0. 0.]
 [0. 0. 0. 1.]
 [1. 0. 0. 0.]
 [0. 0. 0. 0.]
 [0. 0. 0. 0.]
 [0. 0. 0. 0.]]
--------------------------------
iteration 4:
the current total value is: 14.0
the current putting matrix is:
[[1. 0. 0. 0.]
 [0. 0. 0. 1.]
 [1. 0. 0. 0.]
 [0. 0. 0. 0.]
 [0. 1. 0. 0.]
 [0. 0. 0. 0.]]
--------------------------------
--------------------------------
--------------------------------
The final result is:
the finial total value is: 14.0
the finial puttting matrix is:
[[1. 0. 0. 0.]
 [0. 0. 0. 1.]
 [1. 0. 0. 0.]
 [0. 0. 0. 0.]
 [0. 1. 0. 0.]
 [0. 0. 0. 0.]]

bag1 contains:
  good1 has weight of 4 and value of 3
  good3 has weight of 6 and value of 5
bag2 contains:
  good5 has weight of 1 and value of 2
bag3 contains:
bag4 contains:
  good2 has weight of 5 and value of 4

禁忌搜索测试：

1
2
3
goods_set=[goods(4,3),goods(5,4),goods(6,5),goods(7,5),goods(1,2),goods(3,3)]
bags_set=[bags(10),bags(2),bags(1),bags(6)]
result,total_value=multiple_knapsack_tabu(bags_set,goods_set,1)

禁忌搜索测试结果：

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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
--------------------------------
the initial total value is: 0
the initial putting matrix is:
[[0. 0. 0. 0.]
 [0. 0. 0. 0.]
 [0. 0. 0. 0.]
 [0. 0. 0. 0.]
 [0. 0. 0. 0.]
 [0. 0. 0. 0.]]
--------------------------------
iteration 1:
the current total value is: 5.0
the current putting matrix is:
[[0. 0. 0. 0.]
 [0. 0. 0. 0.]
 [1. 0. 0. 0.]
 [0. 0. 0. 0.]
 [0. 0. 0. 0.]
 [0. 0. 0. 0.]]
--------------------------------
iteration 2:
the current total value is: 9.0
the current putting matrix is:
[[0. 0. 0. 0.]
 [0. 0. 0. 1.]
 [1. 0. 0. 0.]
 [0. 0. 0. 0.]
 [0. 0. 0. 0.]
 [0. 0. 0. 0.]]
--------------------------------
iteration 3:
the current total value is: 12.0
the current putting matrix is:
[[1. 0. 0. 0.]
 [0. 0. 0. 1.]
 [1. 0. 0. 0.]
 [0. 0. 0. 0.]
 [0. 0. 0. 0.]
 [0. 0. 0. 0.]]
--------------------------------
iteration 4:
the current total value is: 14.0
the current putting matrix is:
[[1. 0. 0. 0.]
 [0. 0. 0. 1.]
 [1. 0. 0. 0.]
 [0. 0. 0. 0.]
 [0. 1. 0. 0.]
 [0. 0. 0. 0.]]
--------------------------------
iteration 5:
the current total value is: 14.0
the current putting matrix is:
[[0. 0. 0. 0.]
 [0. 0. 0. 1.]
 [1. 0. 0. 0.]
 [0. 0. 0. 0.]
 [0. 1. 0. 0.]
 [1. 0. 0. 0.]]
--------------------------------
iteration 6:
the current total value is: 15.0
the current putting matrix is:
[[0. 0. 0. 0.]
 [0. 0. 0. 0.]
 [0. 0. 0. 1.]
 [1. 0. 0. 0.]
 [0. 1. 0. 0.]
 [1. 0. 0. 0.]]
--------------------------------
iteration 7:
the current total value is: 14.0
the current putting matrix is:
[[0. 0. 0. 0.]
 [0. 0. 0. 1.]
 [0. 0. 0. 0.]
 [1. 0. 0. 0.]
 [0. 1. 0. 0.]
 [1. 0. 0. 0.]]
--------------------------------
iteration 8:
the current total value is: 14.0
the current putting matrix is:
[[0. 0. 0. 0.]
 [0. 0. 0. 1.]
 [1. 0. 0. 0.]
 [0. 0. 0. 0.]
 [0. 1. 0. 0.]
 [1. 0. 0. 0.]]
--------------------------------
iteration 9:
the current total value is: 15.0
the current putting matrix is:
[[0. 0. 0. 0.]
 [0. 0. 0. 0.]
 [0. 0. 0. 1.]
 [1. 0. 0. 0.]
 [0. 1. 0. 0.]
 [1. 0. 0. 0.]]
--------------------------------
iteration 10:
the current total value is: 14.0
the current putting matrix is:
[[0. 0. 0. 0.]
 [0. 0. 0. 1.]
 [0. 0. 0. 0.]
 [1. 0. 0. 0.]
 [0. 1. 0. 0.]
 [1. 0. 0. 0.]]
--------------------------------
iteration 11:
the current total value is: 14.0
the current putting matrix is:
[[0. 0. 0. 0.]
 [0. 0. 0. 1.]
 [1. 0. 0. 0.]
 [0. 0. 0. 0.]
 [0. 1. 0. 0.]
 [1. 0. 0. 0.]]
--------------------------------
iteration 12:
the current total value is: 15.0
the current putting matrix is:
[[0. 0. 0. 0.]
 [0. 0. 0. 0.]
 [0. 0. 0. 1.]
 [1. 0. 0. 0.]
 [0. 1. 0. 0.]
 [1. 0. 0. 0.]]
--------------------------------
iteration 13:
the current total value is: 14.0
the current putting matrix is:
[[0. 0. 0. 0.]
 [0. 0. 0. 1.]
 [0. 0. 0. 0.]
 [1. 0. 0. 0.]
 [0. 1. 0. 0.]
 [1. 0. 0. 0.]]
--------------------------------
iteration 14:
the current total value is: 14.0
the current putting matrix is:
[[0. 0. 0. 0.]
 [0. 0. 0. 1.]
 [1. 0. 0. 0.]
 [0. 0. 0. 0.]
 [0. 1. 0. 0.]
 [1. 0. 0. 0.]]
--------------------------------
--------------------------------
--------------------------------
The final result is:
the finial total value is: 15.0
the finial puttting matrix is:
[[0. 0. 0. 0.]
 [0. 0. 0. 0.]
 [0. 0. 0. 1.]
 [1. 0. 0. 0.]
 [0. 1. 0. 0.]
 [1. 0. 0. 0.]]

bag1 contains:
  good4 has weight of 7 and value of 5
  good6 has weight of 3 and value of 3
bag2 contains:
  good5 has weight of 1 and value of 2
bag3 contains:
bag4 contains:
  good3 has weight of 6 and value of 5

4. 结论

在这个实验中，我实现这三种算法解决了多背包问题。这三种算法都是贪心算法。他们都不能保证找到全局最优解。在这三种算法中，邻居搜索总是能够比贪心算法做得更好，因为邻居搜索尝试了更多的解决方案（其能否找到更好的解决方案很大程度上取决于起点的解决方案，其次是寻找邻居的方式）。而禁忌搜索是一种对于邻居搜索的改良并总是能找到全局最优解（虽然能否找到和tabu list的长度和最大迭代次数有关）。因为禁忌搜索不会陷入局部最优解并能够去寻找更多的解决方案。

  • 本文标题：使用启发式算法解决多背包问题
  • 本文作者：mufiye
  • 创建时间：2021-05-28 22:43:28
  • 本文链接：http://mufiye.github.io/2021/05/28/使用启发式算法解决多背包问题/
  • 版权声明：本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！
 评论