Python基于回溯法解决01背包问题实例

这篇文章主要介绍了Python基于回溯法解决01背包问题,结合实例形式分析了Python回溯法采用深度优先策略搜索解决01背包问题的相关操作技巧,需要的朋友可以参考下

同样的01背包问题，前面采用动态规划的方法，现在用回溯法解决。回溯法采用深度优先策略搜索问题的解，不多说，代码如下：

bestV=0

curW=0

curV=0

bestx=None

defbacktrack(i):

globalbestV,curW,curV,x,bestx

ifi>=n:

ifbestV

bestV=curV

bestx=x[:]

else:

ifcurW w[i]<=c:

x[i]=True

curW =w[i]

curV =v[i]

backtrack(i 1)

curW-=w[i]

curV-=v[i]

x[i]=False

backtrack(i 1)

if__name__=='__main__':

n=5

c=10

w=[2,2,6,5,4]

v=[6,3,5,4,6]

x=[Falseforiinrange(n)]

backtrack(0)

print(bestV)

print(bestx)

运行结果如下：