0-1背包问题——回溯法求解【Python】

回溯法求解0-1背包问题:

问题:背包大小 w,物品个数 n,每个物品的重量与价值分别对应 w[i] 与 v[i],求放入背包中物品的总价值最大。

回溯法核心:能进则进,进不了则换,换不了则退。(按照条件深度优先搜索,搜到某一步时,发现不是最优或者达不到目标,则退一步重新选择)

注:理论上,回溯法是在一棵树上进行全局搜索,但是并非每种情况都需要全局考虑,毕竟那样效率太低,且通过约束+限界可以减少好多不必要的搜索。

解决本问题思路:使用0/1序列表示物品的放入情况。将搜索看做一棵二叉树,二叉树的第 i 层代表第 i 个物品,若剩余空间允许物品 i 放入背包,扩展左子树。若不可放入背包,判断限界条件,若后续继续扩展有可能取得最优价值,则扩展右子树(即此 i 物品不放入,但是考虑后续的物品)。在层数达到物品的个数时,停止继续扩展,开始回溯。

注:如何回溯呢?怎样得到的,怎样恢复。放入背包中的重量取出,加在bagV上的价值减去。

约束条件:放入背包中物品的总质量小于等于背包容量

限界条件:当前放入背包中物品的总价值(i及之前) + i 之后的物品总价值 < 已知的最优值     这种情况下就没有必要再进行搜索

数据结构: 用一个变量记录当前放入背包的总价值 bagV(已扩展),一个变量记录后续物品的总价值 remainV(未扩展),当前已得到的一种最优值 bestV(全局情况),一个用0/1表示的数组bestArr[]记录哪些物品放入了背包。

核心结构:递归思路进行解决。层层递归,递归到尽头,保留最优值,恢复递归中,层层回溯,即将原来加上去的重量与价值恢复。

# -*- coding:utf-8 -*-

def Backtrack(t):
global bestV, bagW, bagV,arr, bestArr, cntV if t > n: #某次深度优先搜索完成
if bestV < bagV:
for i in range(1, n+1):
bestArr[i] = arr[i]
bestV = bagV
else: #深度优先搜索未完成
if bagW + listWV[t][0] <= w: #第t个物品可以放入到背包中,扩展左子树
arr[t] = True
bagW += listWV[t][0]
bagV += listWV[t][1]
Backtrack(t+1)
bagW -= listWV[t][0]
bagV -= listWV[t][1]
if cntV[t] + bagV > bestV: #有搜索下去的必要
arr[t] = False
Backtrack(t+1) if __name__ == '__main__': w = int(input()) #背包大小
n = int(input()) #物品个数 listWV = [[0,0]]
listTemp = []
sumW = 0
sumV = 0 for i in range(n):
listTemp = list(map(int, input().split())) #借助临时list每次新增物品对应的list加入到listWV中
sumW += listTemp[0]
sumV += listTemp[1]
listWV.append(listTemp) #依次输入每个物品的重量与价值 bestV = 0
bagW = 0
bagV = 0
remainV = sumV
arr = [False for i in range(n+1)]
bestArr = [False for i in range(n+1)] cntV = [0 for i in range(n+1)] #求得剩余物品的总价值,cnt[i]表示i+1~n的总价值
cntV[0] = sumV
for i in range(1, n+1):
cntV[i] = cntV[i-1] - listWV[i][1] if sumW <= w:
print(sumV)
else:
Backtrack(1)
print(bestV)
print(bestArr)
print(cntV)

检测:

10
5
2 6
5 3
4 5
2 4
3 6 17
[False, True, False, True, False, True]
[24, 18, 15, 10, 6, 0]
上一篇:破圈法求解最小生成树c语言实现(已验证)


下一篇:PC-1500的代码存入WAV文件