python 动态规划问题解析(背包问题和最长公共子串)
作者:yetangjian 时间:2021-01-21 14:17:24
背包问题
现在要往一个可以装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
标签:python,动态规划,最长公共子串,背包
![](/images/zang.png)
![](/images/jiucuo.png)
猜你喜欢
python绘制立方体的方法
2022-09-26 10:34:14
![](https://img.aspxhome.com/file/2023/7/109407_0s.jpg)
JavaScript实现带自动提示的文本框效果代码
2011-02-05 11:13:00
python中的随机函数小结
2021-07-01 04:26:59
对numpy中数组元素的统一赋值实例
2021-05-31 18:47:37
MYSQL数据库教程:唯一编号
2009-02-27 15:27:00
初衷和结果
2009-02-23 12:52:00
得到元素真实的背景颜色的函数
2008-05-20 12:04:00
Django学习笔记之View操作指南
2023-05-29 14:08:47
在Python中操作字符串之replace()方法的使用
2021-03-15 14:10:59
JSP安全开发之XSS漏洞详解
2023-06-13 13:07:24
![](https://img.aspxhome.com/file/2023/1/62781_0s.png)
python实现微信小程序用户登录、模板推送
2021-10-15 23:25:17
实现php删除链表中重复的结点
2023-09-05 09:36:15
python 控制Asterisk AMI接口外呼电话的例子
2021-07-01 16:59:39
Ubuntu20下的Django安装的方法步骤
2022-05-01 09:07:24
![](https://img.aspxhome.com/file/2023/5/81705_0s.png)
ORACLE8的分区管理
2023-07-13 14:42:43
Python实现数据可视化看如何监控你的爬虫状态【推荐】
2022-07-15 11:50:43
![](https://img.aspxhome.com/file/2023/0/103190_0s.jpg)
如何用Sleep函数编译一个定时组件?
2010-06-13 14:35:00
python随机获取列表中某一元素的方法
2023-08-23 18:25:13
python实现移位加密和解密
2022-03-20 09:09:27
![](https://img.aspxhome.com/file/2023/6/105726_0s.jpg)
python Crypto模块的安装与使用方法
2022-09-17 15:19:01
![](https://img.aspxhome.com/file/2023/7/114487_0s.png)