本文實例講述了Python基于回溯法解決01背包問題。分享給大家供大家參考，具體如下：

同樣的01背包問題，前面采用動態規劃的方法，現在用回溯法解決。回溯法采用深度優先策略搜索問題的解，不多說，代碼如下：

bestV=0curW=0curV=0bestx=Nonedef backtrack(i):  global bestV,curW,curV,x,bestx  if i>=n:    if bestV<curV:      bestV=curV      bestx=x[:]  else:    if curW+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=[False for i in range(n)]  backtrack(0)  print(bestV)  print(bestx)

運行結果如下：

更多關于Python相關內容感興趣的讀者可查看本站專題：《Python數據結構與算法教程》、《Python加密解密算法與技巧總結》、《Python編碼操作技巧總結》、《Python函數使用技巧總結》、《Python字符串操作技巧匯總》及《Python入門與進階經典教程》

希望本文所述對大家Python程序設計有所幫助。