python 动态规划问题解析(背包问题和最长公共子串)
作者:yetangjian 发布时间:2021-01-21 14:17:24
标签:python,动态规划,最长公共子串,背包
背包问题
现在要往一个可以装4个单位重量的背包里怎么装价值最高:A重量1个单位,价值15;B重量3个单位,价值20;C重量4个重量,价值30
使用动态规划填充空格
class SolutionBag:
def valuableBag(self,optionalList,sizeBig):
#创建网格
grid = [[0 for i in range(sizeBig+1)] for j in range(len(optionalList)+1)]
#从行列序号1开始计数
column = 1
for v in optionalList.values():
optionalWeight,optionalPrice = v
for row in range(sizeBig):
if optionalWeight > row+1:
grid[column][row+1] = grid[column-1][row+1]
else:
grid[column][row+1] = max(grid[column-1][row+1],optionalPrice+grid[column-1][row+1-optionalWeight])
column += 1
return grid#SolutionBag().valuableBag({"A":(1,15),"B":(3,20),"C":(4,30)},4)
最长公共子串
在动态规划中,你要将某个指标最大化。在这个例子中,你要找出两个单词的最长公共子串。fish和fosh都包含的最长子串是什么呢
如何将这个问题划分为子问题呢?你可能需要比较子串:不是比较hish和fish,而是先比较his和fis
我们网格填充的方法来实现
#伪代码
#字母相同则左上方+1
if word1[i] == word2[j] :
cell[i][j] = cell[i-1][j-1] +1
else:
cell[i][j] = max(cell[i][j-1],cell[i-1][j])
python实现网格
class SolutionLengthS:
def longestLength(self,str1,str2):
grid = [[0 for j in range(len(str2)+1)] for i in range(len(str1)+1)]
for i in range(len(str2)):
for j in range(len(str1)):
if str1[j] == str2[i] :
grid[i+1][j+1] = grid[i][j] + 1
else:
grid[i+1][j+1] = max(grid[i+1][j],grid[i][j+1])
return grid
来源:https://www.cnblogs.com/yetangjian/p/16268741.html


猜你喜欢
- 环境:python3 + unittest + requestsExcel管理测试用例,HTMLTestRunner生成测试报告测试完成后邮
- python PIL图像处理模块中的ImageDraw类支持各种几何图形的绘制和文本的绘制,如直线、椭圆、弧、弦、多边形以及文字等。下面直接
- Python使用称为Python Path的搜索路径来查找使用import语句导入代码的模块。大多数代码只会汇入已经默认路径上的模块,通过安
- 看代码: <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional
- 主要功能在copyFiles()函数里实现,如下:def copyFiles(src, dst): sr
- 1、如果之前已经安装我们先卸载一下yum -y remove php*2、由于linux的yum源不存在php7.x,所以我们要更改yum源
- 这是一个很久以前的例子,现在在整理资料时无意发现,就拿出来再改写分享。1.需求 1.1 基本需求: 根据输入的地址关键字,搜索出完
- 1.效果2.环境1.pytorch2.visdom3.python3.53.用到的代码# coding:utf8import torchfr
- 前言弹幕可以给观众一种“实时互动”的错觉,虽然不同弹幕的发送时间有所区别,但是其只会在视频 * 定的一
- 朋友去面试。对方问他:说说你之前做的那个站,有什么地方好的?朋友就说:用户体验比别的站好。对方又问:你怎么知道用户体验比别的好?朋友于是又磕
- 如何获取一个网站的相关信息,获取赶集网的招聘信息,本文为大家介绍利用python获取赶集网招聘信息的关键代码,供大家参考,具体内容如下imp
- 表达式的优先级表达式(Expression)是运算符(operator)和操作数(operand)所构成的序列代码段a = 1b = 2c
- 在编程领域里,枚举用来表示只包含有限数量的固定值的类型,在开发中一般用于标识错误码或者状态机。拿一个实体对象的状态机来说,它通常与这个对象在
- 我正在参加天池上的一个竞赛,刚开始用的是DenseNet121但是效果没有达到预期,因此开始尝试使用模型融合,将Desenet和Xcepti
- xml即可扩展标记语言,它可以用来标记数据、定义数据类型,是一种允许用户对自己的标记语言进行定义的源语言。从结构上,很像HTML超文本标记语
- 最近好多伙伴说,我用vue做的项目本地是可以的,但部署到服务器遇到好多问题:资源找不到,直接访问index.html页面空白,刷新当前路由4
- 本文实例讲述了Python实现的爬取百度文库功能。分享给大家供大家参考,具体如下:# -*- coding: utf-8 -*-from s
- 正则表达式,又称正规表示法、常规表示法(英语:Regular Expression,在代码中常简写为regex、regexp或RE),计算机
- MySQL是一个关系型数据库管理系统,由瑞典MySQL AB 公司开发,属于 Oracle 旗下产品。MySQL 是最流行的关系型数据库管理
- 有这样一类文章标题,喜欢学习的人肯定见过:使用Google的7个技巧Web设计中9个常见的可用性错误Adobe Photoshop 75个技