Python基于动态规划算法解决01背包问题实例
作者：littlethunder 发布时间：2021-01-10 21:22:26
标签：Python,动态规划,背包问题
本文实例讲述了Python基于动态规划算法解决01背包问题。分享给大家供大家参考，具体如下：
在01背包问题中，在选择是否要把一个物品加到背包中，必须把该物品加进去的子问题的解与不取该物品的子问题的解进行比较，这种方式形成的问题导致了许多重叠子问题，使用动态规划来解决。n=5是物品的数量，c=10是书包能承受的重量，w=[2,2,6,5,4]是每个物品的重量，v=[6,3,5,4,6]是每个物品的价值，先把递归的定义写出来：
然后自底向上实现，代码如下：
def bag(n,c,w,v):
res=[[-1 for j in range(c+1)] for i in range(n+1)]
for j in range(c+1):
res[0][j]=0
for i in range(1,n+1):
for j in range(1,c+1):
res[i][j]=res[i-1][j]
if j>=w[i-1] and res[i][j]<res[i-1][j-w[i-1]]+v[i-1]:
res[i][j]=res[i-1][j-w[i-1]]+v[i-1]
return res
def show(n,c,w,res):
print('最大价值为:',res[n][c])
x=[False for i in range(n)]
j=c
for i in range(1,n+1):
if res[i][j]>res[i-1][j]:
x[i-1]=True
j-=w[i-1]
print('选择的物品为:')
for i in range(n):
if x[i]:
print('第',i,'个,',end='')
print('')
if __name__=='__main__':
n=5
c=10
w=[2,2,6,5,4]
v=[6,3,5,4,6]
res=bag(n,c,w,v)
show(n,c,w,res)
输出结果如下：
希望本文所述对大家Python程序设计有所帮助。
来源：http://blog.csdn.net/littlethunder/article/details/26575417
0
投稿猜你喜欢
1.今天网上下载一个博客项目，发现本地访问,js,css加载不了.我想应该是项目上线的安全措施,但是我想调试项目.找到方法如下在settin- 看过一篇关于下载网页中图片的文章，它只能下载以http头的图片，我做了些改进，可以下载网页中的所有连接资源，并按照网页中的目录结构建立本地目
- 几乎在学习、使用任何一种编程语言的时候，关于socket的练习从来都不会少，尤其是会写一些局域网的通信的东西。所以书上的这个项目刚好可以练习
- 阅读上一篇：你是真正的用户体验设计者吗? Ⅵ很可怕，是吧！图中翻译：（从内到外）第一层：用户体验第二层：内容管理界面设计顾客关系管理交互设计
- 1 逻辑数据库和表的设计数据库的逻辑设计、包括表与表之间的关系是优化关系型数据库性能的核心。一个好的逻辑数据库设计可以为优化数据库和应用程序
- 为什么能实现在线编辑呢? 首先需要ie 的支持，在 ie 5.5以后就有一个编辑状态，就是利用这个编辑状态,然后用javascript 来控
- 一个改进的仿google页面拖拽效果，移植方便。web2.0网站经常会用有这个拖拽页面布局的功能，如果你也想给你的网站加上这个有趣的功能，不
- 安装需要的包1 第一步:全文检索不同于特定字段的模糊查询，使用全文检索的效率更高，并且能够对于中文进行分词处理。haystack：全文检索的
- 本文实例讲述了php计算给定日期所在周的开始日期和结束日期。分享给大家供大家参考，具体如下：<?php/** * 取得给定日期所在周的
- 要达到二级名的效果，必须一下条件以及流程：1、必须有一个顶级域名，而且此域名必须做好泛解析并做好指向。2、必须有一台属于你的独立的服务器。泛
- 对url进行编码在服务器端我们可以使用asp中的server.urlencode，很方便实现。如：<％ ss="asp之家欢
- 翻译整理：Young.J；官方网站：http://jquery.comjQuery是一款同prototype一样优秀js开发库类，特别是对c
- 这是一套适用于JavaScript程序的编码规范。它基于Sun的Java程序编码规范。但进行了大幅度的修改, 因为JavaScript不是J
- 本文实例为大家分享了python实现定时发送邮件的具体代码，供大家参考，具体内容如下一、发送邮件import smtplib from em
- 在操作DataFrame时，肯定会经常用到loc，iloc，at等函数，各个函数看起来差不多，但是还是有很多区别的，我们一起来看下吧。首先，
- 前言事情是这样的：今天晚上，女朋友让我十二点催她睡觉。不过，可是我实在太困了，熬不下去…… 是吧
- 1. document.form.item 问题 (1)现有问题：现有代码中存在许多 document.formName.item(&quo
- 配置要求：IIS（win2000 server 自带）、Java 2 SDK 1.4.2 (或更高版本)、Tomcat Web Server
- 本文实例讲述了Python基于正则表达式实现文件内容替换的方法。分享给大家供大家参考，具体如下：最近因为有一个项目需要从普通的服务器移植到S
- 如何让animate在显示图片的过程保持窗口的标题不变animate -title "My Image Sequence"
