四种方法解0-1背包问题-基于python
文章目录
网上关于这个方面的python代码比较少，所以分别用暴力、动态规划、回溯、分支限界实现了一下关于0-1背包问题(不能只取一部分物品)。
1.暴力法
1.1 设计思想
蛮力法即找出所有可能的解，在所有的解中选择最优解。由于物品众多，不可能采用for循环的形式，所以这个实验考虑使用递归调用的方式找出所有满足条件的解，设置一个记录最大价值的变量valuesMax记录最优解时的价值，设置一个visitMax数据记录最优解时物品的状态是否装入背包。具体的递归过程设计为：从第一个物品开始遍历所有的物品，在每次遍历中，判断物品是否装入，如果没有装入，判断背包的剩余容量能否装入此物品，如果可以，则将visit[i]置为1，然后更新背包剩余容量，进行递归调用。每次进入递归函数时，将当前的背包价值与valuesMax进行比较，如果当前值大于valuesMax，则将当前值赋值给valuesMax，并将visit赋值给visitMax。
1.2代码实现
#蛮力法解0/1背包问题
import numpy as np
class brute:
def __init__(self, w, v, c):
'''
:param w: 重量
:param v: 价值
:param c: 背包容量
'''
self.w = w
self.v = v
self.c = c
def brute_force(self, visit, values, currentV):
'''
:param visit: 记录物品装或者不装的数组
:param values: 记录当前的价值
:param currentV: 记录当前的体积
:return:
'''
global visitMax #全局变量，记录最大价值时物品的状态全
global valuesMax #局变量，记录最大价值
if(values > valuesMax):
valuesMax = values
visitMax = visit.copy()
self.v = np.array(self.v)
self.w = np.array(self.w)
for i in range(self.v.size):
if(visit[i] == 0):
if(self.w[i] > self.c - currentV):
continue
visit[i] = 1
self.brute_force(visit, values+self.v[i], currentV+self.w[i])
visit[i] = 0
return visit, values
b = brute(w=[6,5,4,1,2,3,9,8,7], v=[1,2,3,7,8,9,6,5,4], c=20)
visit = np.zeros(9)
valuesMax = 0
visitMax = visit.copy()
status = []
x = b.brute_force(visit, 0, 0)
for i in range(visitMax.size):
if(visitMax[i] != 0):
status.append(i+1)
print("最优解序号为：")
print(status)
print("最大值为：")
print(valuesMax)
1.3 实验结果
2.动态规划
2.1设计思想
使用动态规化填表。先求出最大值，定义了一个dynamic_programming返回值为建立的表。先建立表values[nums+1,c+1]，行为第i个物品，列为背包容量，初始化，将values[i,0]与values[0,i]置为零。然后对于第i个物品开始，values[i,j]的值分为两种情况，如果背包得剩余容量不够当前物品得重量，则values[i,j]=values[i,j-1]；如果当前剩余容量大于当前物品的重量，则如果(values[i-1, j] > values[i-1, j-=w[i - 1]] + =v[i - 1])，则values[i,j] = values[i-1, j]，否则，values[i,j] = values[i-1, j-=w[i - 1]] + =v[i - 1]。values[num,c]即为最优值。对于找最优解下的每个物品的状态，设计一个load_which方法来判断，则从values[num,c]开始判断values[i,c] =是否等于values[i-1,c]，不等于的话，则代表当前的i装入背包，最后返回一个列表，里面的值代表物品已选择。
2.2 代码实现
#动态规化解0/1背包问题
import numpy as np
class onezerobag:
def __init__(self, w, v, c):
'''
:param w: 物体价值
:param v: 物体重量
:param c: 背包容量
'''
self.w = w
self.v = v
self.c = c
def dynamic_programming(self):
self.v = np.array(self.v)
self.w = np.array(self.w)
num = self.v.size #物体数量
values = np.zeros([num+1, self.c+1])
for i in range(values.shape[0]):
values[i, 0] = 0
for i in range(values.shape[1]):
values[0, i] = 0
for i in range(1, values.shape[0], 1):
for j in range(1, values.shape[1], 1):
if(self.w[i - 1] > j): #如果物体重量大于包当前重量，不装进去
values[i,j] = values[i-1, j]
else:
if(values[i-1, j] > values[i-1, j-self.w[i - 1]] + self.v[i - 1]):
values[i,j] = values[i-1, j]
else:
values[i,j] = values[i-1, j-self.w[i - 1]] + self.v[i - 1]
print("表格为：")
for i in range(0, values.shape[0], 1):
for j in range(0, values.shape[1], 1):
print(values[i,j], end = " ")
print()
return values
def load_which(self, values):
h = values.shape[0]
c = self.c
which = []
for i in range(h-1, 0, -1):
if(values[i,c] == values[i-1,c]):
continue
else:
which.append(i)
c = c - self.w[i - 1]
which.reverse()
return which, values[values.shape[0]-1, values.shape[1]-1]
question = onezerobag(w=[6,5,4,1,2,3,9,8,7], v=[1,2,3,7,8,9,6,5,4], c=20)
x = question.load_which(question.dynamic_programming())
print("最优解序号为：")
print(x[0])
print("最大值为：")
print(x[1])
2.3实验结果
3.回溯
3.1设计思想
设计思想回溯法设计子集树来搜索最优解。定义一个back_tracking方法来进行回溯，对于每一个物品有选择和不选择两种方案。在搜索的过程中，可以进行剪枝操作，对于不选的物品，计算如果不选择此物品下的所能达到的最大价值是否可以比当前搜索到的最优价值还大，如果不能大于当前的最优价值，则进行剪枝操作，即不在继续向下搜索这个结点的子树。对于选择的物品，判断背包的剩余重量是否大于当前物品的重量，如果小于当前物品的重量，则不装入，不继续搜索。设计一个上界方法bound，来判断当前物品下所能达到的最大价值：将物品的单位价值从大到小进行排列，然后搜索从当前物品开始将剩余物品填满背包，求上界时物品将背包完全填满，也就是说，可以装入一部分，判断是否大于当前的最优价值，如果不能，则不继续搜索。在搜索过程中，采用深度优先的方式进行搜索，即先搜索左子树，在搜索右子树。最后back_tracking返回记录物品是否装入的数组与最优价值。
3.2代码实现
import numpy as np
class backTrackingMethod:
def __init__(self, w, v, c, cw, cp, bestp):
'''
:param w: 价值
:param v: 体积
:param c: 背包容量
'''
self.w = np.array(w)
self.v = np.array(v)
self.c = c
self.cw = cw
self.cp = cp
self.bestp = bestp
def value_per(self):
'''
求单位质量大小 并降序排列
:return:
'''
per = self.v / self.w
sor = np.sort(per)
index = np.argsort(per)
list = []
for i in sor:
list.append(i)
list.reverse()
list1 = []
for i in index:
list1.append(i)
list1.reverse()
index = np.array(list1)
a = self.v.copy()
b = self.w.copy()
for i in range(self.v.size):
a[i] = self.v[index[i]]
b[i] = self.w[index[i]]
self.v = a.copy()
self.w = b.copy()
return self.v, self.w, index
#定义上界函数
def bound(self, i):
leftw = self.c - self.cw
bestbound = self.cp
while (i < self.v.size):
if (self.w[i] <= leftw):
bestbound = bestbound + self.v[i]
leftw = leftw - self.w[i]
i += 1
else:
bestbound = bestbound + self.v[i] / self.w[i] * leftw
break
return bestbound
def back_tracking(self, i, visit):
if(i > self.v.size-1):
self.bestp = self.cp
return
if(self.cw + self.w[i] < self.c):
self.cw += self.w[i]
self.cp += self.v[i]
visit[i] = 1
self.back_tracking(i+1, visit)
self.cw -= self.w[i]
self.cp -= self.v[i]
else:
visit[i] = 0
if(self.bound(i+1) >= self.bestp):
self.back_tracking(i+1, visit)
return visit, self.bestp
visit = np.zeros(9)
question = backTrackingMethod(w=[6, 5, 4, 1, 2, 3, 9, 8, 7], v=[1, 2, 3, 7, 8, 9, 6, 5, 4], c=20, cw = 0, cp = 0 ,bestp=0)
w, v, index = question.value_per()
visit, best = question.back_tracking(0, visit)
list = []
for i in range(visit.size):
if(visit[i] != 0):
list.append(index[i]+1)
print("最优解序号为：")
print(list)
print("最大价值为：")
print(best)
3.3实验结果
4.分支限界法
4.1设计思想
分支限界法与回溯法最大的不同在与分支限界使用的广度优先搜索，在这里我设计了一棵树，(回溯法里面的树是我没有真正地设计，直接进行递归调用回溯的方法来表示深度搜索)，树的结点包括：当前的最优价值，当前的背包重量，当前的物品序号，当前结点的最优上界，当前结点的父结点，当前物品状态。在设计上界函数bound时大致与回溯法的上界函数相同，思想是一致的，但是由于我设计的树结点，所以上界函数传入的是结点。剪枝操作与回溯法的剪枝操作完全相同，即不在继续向下搜索这个结点的子树。对于选择的物品，判断背包的剩余重量是否大于当前物品的重量，如果小于当前物品的重量，则不装入，不继续搜索。设计一个上界方法bound，来判断当前物品下所能达到的最大价值：将物品的单位价值从大到小进行排列，然后搜索从当前物品开始将剩余物品填满背包，求上界时物品将背包完全填满，也就是说，可以装入一部分，判断是否大于当前的最优价值，如果不能，则不继续搜索。branch_bound_method方法返回的是最优值，以及用python集合表示的最优解下的物品状态。
4.2代码实现
#分支限界法
import numpy as np
class branchbound:
def __init__(self, w, v, c, cw, cp, bestx):
self.w = np.array(w)
self.v = np.array(v)
self.c = c
self.cw = cw
self.cp = cp
self.bestx = bestx
def value_per(self):
'''
求单位质量大小 并降序排列
:return:
'''
tempC = 0
per = self.v / self.w
sor = np.sort(per)
index = np.argsort(per)
list = []
for i in sor:
list.append(i)
list.reverse()
list1 = []
for i in index:
list1.append(i)
list1.reverse()
index = np.array(list1)
a = self.v.copy()
b = self.w.copy()
for i in range(self.v.size):
a[i] = self.v[index[i]]
b[i] = self.w[index[i]]
self.v = a.copy()
self.w = b.copy()
return self.v, self.w, index
#定义上界函数，注意这里使用了树结构，所以上界函数与回溯法的上界函数有点不同
def bound(self, i, node1):
leftw = self.c - node1.currv
bestbound = node1.currw
while(i < self.v.size):
if(self.w[i] < leftw):
bestbound = bestbound + self.v[i]
leftw = leftw - self.w[i]
i += 1
else:
bestbound = bestbound + self.v[i] / self.w[i] * leftw
break
return bestbound
def branch_bound_method(self, ind):
list = []
bestindex = set()
list.append(node(0, 0, 0, None, -1))
while(list != []):
node1 = list.pop(0)
if(node1.index < self.v.size):
leftv = node1.currv + self.w[node1.index]
leftw = node1.currw + self.v[node1.index]
left = node(leftv, leftw, node1.index+1, node1, 1)
left.flag = 1
left.up = self.bound(left.index, left)
if(left.currv < self.c):
list.append(left)
if(left.currw > self.bestx):
self.bestx = left.currw
if(left.currw == left.currw):
node2 = left
while(node2.flag != -1):
bestindex.add(ind[node2.index-1] + 1)
node2 = node2.father
right = node(node1.currv, node1.currw, node1.index+1, node1, 0)
right.flag = 0
right.up = self.bound(right.index, right)
if(right.up >= self.bestx):
list.append(right)
return self.bestx, bestindex
class node: #定义树结点
def __init__(self, v, w, index, father, flag):
self.currv = v
self.currw = w
self.index = index
self.up = 0
self.father = father
self.flag = flag
question = branchbound(w=[6, 5, 4, 1, 2, 3, 9, 8, 7], v=[1, 2, 3, 7, 8, 9, 6, 5, 4], c=20, cw = 0, cp = 0 ,bestx=0)
w, v, ind = question.value_per()
bestp, bestindex = question.branch_bound_method(ind)
print("最优解索引：")
print(bestindex)
print("最大价值为：")
print(bestp)
4.3实验结果
本文地址：https://blog.csdn.net/weixin_45490507/article/details/107282739