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

时间:2022-10-30 20:27:04

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)

运行结果如下:

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