python 动态规划问题解析(背包问题和最长公共子串)

作者:yetangjian 时间:2021-01-21 14:17:24 

背包问题

现在要往一个可以装4个单位重量的背包里怎么装价值最高:A重量1个单位,价值15;B重量3个单位,价值20;C重量4个重量,价值30

使用动态规划填充空格

python 动态规划问题解析(背包问题和最长公共子串)

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

我们网格填充的方法来实现

python 动态规划问题解析(背包问题和最长公共子串)

#伪代码
#字母相同则左上方+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,动态规划,最长公共子串,背包
0
投稿

猜你喜欢

  • Python 3.x基于Xml数据的Http请求方法

    2021-05-17 23:45:18
  • JS 替换和时间插件的结合使用方法

    2013-08-19 16:50:31
  • Python入门教程(一)Python简单介绍

    2023-10-25 03:19:16
  • Python删除windows垃圾文件的方法

    2023-08-24 15:38:23
  • Python实现数字的格式化输出

    2021-10-11 18:11:27
  • Python 随机生成中文验证码的实例代码

    2022-12-15 23:17:34
  • numpy.insert用法及内插插0的方法

    2023-03-28 10:06:13
  • 微信小程序(十二)text组件详细介绍

    2024-04-19 09:43:53
  • 关于长度单位pt、px、dpi的误解

    2008-06-01 13:30:00
  • python的json中方法及jsonpath模块用法分析

    2021-10-06 08:21:32
  • 关于使用PLSQL Developer时出现报错ora-12514的问题

    2024-01-15 09:12:17
  • asp 得到动态数组中元素的个数

    2011-03-30 10:55:00
  • Go 实战单队列到优先级队列实现图文示例

    2024-05-22 10:19:03
  • Python代码块批量添加Tab缩进的方法

    2022-10-10 16:41:39
  • Vue3-KeepAlive,多个页面使用keepalive方式

    2024-05-02 16:33:39
  • Vue中子组件调用父组件的3种方法实例

    2024-05-13 09:08:18
  • layDate插件设置开始和结束时间

    2024-05-03 15:05:03
  • ML神器:sklearn的快速使用及入门

    2023-04-17 04:42:09
  • 详解php中反射的应用

    2023-11-15 01:26:56
  • 如何利用JSHint减少JavaScript的错误

    2024-05-28 15:37:40
  • asp之家 网络编程 m.aspxhome.com