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
投稿猜你喜欢
经过一轮的项目封闭开发，页面制作的动手能力提高了不少，用AW的话说就是被复杂的东西虐过以后很多问题都变得容易了，的确很有道理。我个人觉得技术- 作者：F. Permadi译者：Sheneyan(子乌)英文原文： INTRODUCTION TO JavaScript Functions
- 这学期在学习编译原理，最近的上机作业就是做一个简单的词法分析器，在做的过程中，突然有个需求就是判断一个字符串是否为合法的标示符，因为我是用p
- 对于从事数据领域的小伙伴来说，当需要阐述自己观点、展示项目成果时，我们需要在最短时间内让别人知道你的想法。我相信单调乏味的语言很难让别人快速
- Python——re模块 简介定义：re模块称为正则表达式；作用：创建一个"规则表达式"，用于验证和查找符合规
- Pycharm - Python 开发工具通过 agent 代理使用1、下载 Pycharm下载地址2、支持本代理包支持 2020 版本3、
- 进行已经矢量化后的字符串数据，可以使用pandas的Series数据对象的map方法。这样，对于未经矢量化的数据也可以先进行数据的矢量化转换
- 换脸！这段时间，deepfakes搞得火热，比方说把《射雕英雄传》里的朱茵换成了杨幂，看下面的图！毫无违和感！其实早在之前，基于AI换脸的技
- 前言在本文中，我将展示如何将对象从一个图像添加到另一个图像。为此，我们需要:1.背景图像;2.对象3.对象的mask(mask为黑色，其他空
- 前言需要注意，对实例化的文本组件的insert、delete等操作的index**都是浮点型而不是整型**，（1.0，2.0）表示的是对第一
- IE 的弹窗常用的有两种，不外乎是 window.open 与 window.showModalDialog，前者兼容性好，后者
- 代码如下:title=request("title") title=replace(title,"chr(3
- 1. 图像缩放1.2. 使用命令import cv2# 缩放def resize(img, k, inter):
- def ddns():"""用当前ip更新ddns"""headers = {&
- BCP语句的作用：BCP是SQL提供的进行数据传输的实用程序，这种语句提供了非常快的数据导入的方法。（当然7。0也有BCP的替代方法就是DT
- Microsoft SQL Server 2008将包含用于合并两个行集(rowset)数据的新句法。根据一个源数据表对另一个数据表进行确定
- Windows中升级MySQL应采取的步骤：1. 进行升级前你应先备份当前的MySQL安装。2. 下载最新Windows版MySQL。3.
- 如题,在控制台运行python manage.py startapp sales 建立一个应用报错异常1.应用名不能包含下划线等字符 所以a
- 我要实现的就是下图的这种样式，可参考下面这两个网站的留言板，他们的实现原理都是一样的畅言留言板样式：网易跟帖样式：原理需要在评论表添加两个主
- 一、概述Python Flask 是一个轻量级的 Web 框架，它提供了一个易于使用的 API 来创建 Web 应用程序。在 Flask 中
