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随机生成库faker库api实例详解

废话不多说,直接上代码! # -*- coding: utf-8 -*- # @Author : FELIX # @Date : 2018/6/30 9:49 from fake...

Python简单实现Base64编码和解码的方法

本文实例讲述了Python简单实现Base64编码和解码的方法。分享给大家供大家参考,具体如下: Base64编码是一种“防君子不防小人”的编码方式。广泛应用于MIME协议,作为电子邮件...

Python中生成器和yield语句的用法详解

 在开始课程之前,我要求学生们填写一份调查表,这个调查表反映了它们对Python中一些概念的理解情况。一些话题("if/else控制流" 或者 "定义和使用函数")对于大多数学...

Python面向对象基础入门之设置对象属性

前言 前面我们已经介绍了 python面向对象入门教程之从代码复用开始(一) ,这篇文章主要介绍的是关于Python面向对象之设置对象属性的相关内容,下面话不多说了,来一起看看...

python调用webservice接口的实现

python调用webservice接口的实现

使用suds这个第三方模块 from suds.client import Client url = 'http://ip:port/?wsdl' cilent=Client...