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

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

概述回溯求解0-1背包问题: 问题:背包大小 w,物品个数 n,每个物品的重量与价值分别对应 w[i] 与 v[i],求放入背包中物品的总价值最大。 回溯法核心:能进则进,进不了则换,换不了则退。(按照条件深度优先搜索,搜到某一步时,发现不是最优或者达不到目标,则退一步重新选择) 注:理论上,回溯法是在一棵树上进行全局搜索,但是并非每种情况都需要全局考虑,毕竟那样效率太低,且通过约束+限界可以减少好

回溯法求解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)

 

检测:

1052 65 34 52 43 617[False,True,False,True][24,18,15,10,6,0]
总结

以上是内存溢出为你收集整理的0-1背包问题——回溯法求解【Python】全部内容,希望文章能够帮你解决0-1背包问题——回溯法求解【Python】所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错,欢迎将内存溢出网站推荐给程序员好友。

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/langs/1195607.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-06-03
下一篇 2022-06-03

发表评论

登录后才能评论

评论列表(0条)

保存