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

yipeiwu_com5年前Python基础

本文实例讲述了Python基于回溯法解决01背包问题。分享给大家供大家参考,具体如下:

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

bestV=0
curW=0
curV=0
bestx=None
def 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程序设计有所帮助。

相关文章

Python实现提取谷歌音乐搜索结果的方法

本文实例讲述了Python实现提取谷歌音乐搜索结果的方法。分享给大家供大家参考。具体如下: Python的简单脚本,用于提取谷歌音乐搜索页面中的歌曲信息,包括歌曲名,作者,专辑名,现在链...

Python生成器以及应用实例解析

本文研究的主要是Python生成器及其应用,具体如下。 一、定义 可以理解为一种数据类型,这种数据类型自动实现了迭代器协议(其他的数据类型需要调用自己内置的__iter__方法),所以生...

Python struct.unpack

1. 设置fomat格式,如下: 复制代码 代码如下:# 取前5个字符,跳过4个字符华,再取3个字符 format = '5s 4x 3s' 2. 使用struck.unpack获取子字...

python self,cls,decorator的理解

1. self, cls 不是关键字 在python里面,self, cls 不是关键字,完全可以使用自己写的任意变量代替实现一样的效果 代码1 复制代码 代码如下:class MyTe...

Python读取Excel表格,并同时画折线图和柱状图的方法

Python读取Excel表格,并同时画折线图和柱状图的方法

今日给大家分享一个Python读取Excel表格,同时采用表格中的数值画图柱状图和折线图,这里只需要几行代码便可以实。 首先我们需要安装一个Excel操作的库xlrd,这个很简单,在安装...