Python基于回溯法解决01背包问题实例
作者：littlethunder 发布时间：2023-08-04 01:09:04
标签：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程序设计有所帮助。
来源：http://blog.csdn.net/littlethunder/article/details/26621427
0
投稿猜你喜欢
- 数据库开发数据库应用，选择一个好的数据库是非常重要的。下面从一些方面比较了SQL Server与Oracle、DB2三种数据库，为你选择数据
- 如何用SysOjects来获知数据库的信息？SysObjects中就保存了数据库中所有对象的信息，如：SELECT * FROM SysOb
- 文件操作1#文件操作流程：1、打开文件，得到一个文件句柄；通过文件句柄操作文件；关闭文件。#将文件打开文件赋给file1，test_file
- 这篇文章主要介绍了Python中join（）函数多种操作代码实例,文中通过示例代码介绍的非常详细，对大家的学习或者工作具有一定的参考学习价值
- 如果你电脑是Mac的，使用homebrew安装MySQL是一个非常便捷的方式，但是还是会出现一些问题；首先保证你已经安装了mysql,如果是
比如 1--1 2--1- create 语句后面的TYPE=MyISAMTYPE=MyISAM 和 ENGINE=MyISAM 都是设置数据库存储引擎的语句 ，(老版
- 一、查询条件精确，针对有参数传入情况 二、SQL逻辑执行顺序 FROM-->JOIN-->WHERE-->GROUP--&
- 什么是机器学习 （Machine Learning） 机器学习是研究计算机怎样模
- 在这篇asp之数学函数里，我们将会以表格的形式，让大家了解到关于ASP中能用到的数学函数，里面包括一个数的绝对值、一个数的平方根
- <script language="javascript"><!-- var&n
- 1、查看当前数据库支出的存储引擎方法1：mysql> show engines \G;************************
- 前言MySQL支持单机事务的良好表现毋庸置疑，那么在分布式系统中，涉及多个节点，MySQL又是如何实现分布式事务的呢？比如开发一个业务系统，
- 这篇文章主要介绍了Python读取表格类型文件代码实例,文中通过示例代码介绍的非常详细，对大家的学习或者工作具有一定的参考学习价值,需要的朋
- 1、超时时间以下这些配置项单位都是秒，在mysql命令行中可以使用show global variables like '变量名&#
- 题目:来自Madrid且订单数少于3的消费者 建表:set nocount on --当 SET NOCOUNT 为
- 说到装饰器，就不得不说python自带的三个装饰器：1、@property 将某函数，做为属性使用@property 修饰，就是将方法，变成
- 使用scrapy爬取了网上的一些数据，存储在了mysql数据库中，想使用Django将数据展示出来，在网上看到都是使用Django的mode
- 前言本章我们来介绍如何使用Pytorch训练一个区分不同音频的分类模型，例如你有这样一个需求，需要根据不同的鸟叫声识别是什么种类的鸟，这时你
- 这年头如果用 python3 做条形码的，肯定（推荐）用 pystrich 。这货官方文档貌似都没写到支持 Code128 ，但是居然有这个
