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

概述回溯法求解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】所遇到的程序开发问题。

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