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

到此这篇关于python 动态规划（背包问题和最长公共子串）的文章就介绍到这了,更多相关python 动态规划内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • Python基于动态规划算法解决01背包问题实例

    Python基于动态规划算法解决01背包问题实例

    本文实例讲述了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): re

  • python动态规划算法实例详解

    如果大家对这个生僻的术语不理解的话,那就先听小编给大家说个现实生活中的实际案例吧,虽然现在手机是相当的便捷,还可以付款,但是最初的时候,我们经常会使用硬币,其中,我们如果遇到手中有很多五毛或者1块钱硬币,要怎么凑出来5元钱呢?这么一个过程也可以称之为动态规划算法,下面就来看下详细内容吧. 从斐波那契数列看动态规划 斐波那契数列:Fn = Fn-1 + Fn-2 ( n = 1,2 fib(1) = fib(2) = 1) 练习:使用递归和非递归的方法来求解斐波那契数列的第 n 项 代码如下: #

  • python实现对求解最长回文子串的动态规划算法

    基于Python实现对求解最长回文子串的动态规划算法,具体内容如下 1.题目 给定一个字符串 s,找到 s 中最长的回文子串.你可以假设 s 的最大长度为1000. 示例 1: 输入: "babad" 输出: "bab" 注意: "aba"也是一个有效答案. 示例 2: 输入: "cbbd" 输出: "bb" 2.求解 对于暴力求解在这里就不再骜述了,着重介绍如何利用动态规划算法进行求解. 关于动态规划的含

  • 动态规划之矩阵连乘问题Python实现方法

    动态规划之矩阵连乘问题Python实现方法

    本文实例讲述了动态规划之矩阵连乘问题Python实现方法.分享给大家供大家参考,具体如下: 给定n个矩阵{A1,A2,-,An},其中Ai与Ai+1是可乘的,i=1,2 ,-,n-1.如何确定计算矩阵连乘积的计算次序,使得依此次序计算矩阵连乘积需要的数乘次数最少. 例如: A1={30x35} ; A2={35x15} ;A3={15x5} ;A4={5x10} ;A5={10x20} ;A6={20x25} ; 结果为:((A1(A2A3))((A4A5)A6))  最小的乘次为15125.

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

    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开始

  • Python最长公共子串算法实例

    本文实例讲述了Python最长公共子串算法.分享给大家供大家参考.具体如下: #!/usr/bin/env python # find an LCS (Longest Common Subsequence). # *public domain* def find_lcs_len(s1, s2): m = [ [ 0 for x in s2 ] for y in s1 ] for p1 in range(len(s1)): for p2 in range(len(s2)): if s1[p1] =

  • 深入解析最长公共子串

    深入解析最长公共子串

    题目:如果字符串一的所有字符按其在字符串中的顺序出现在另外一个字符串二中,则字符串一称之为字符串二的子串.注意,并不要求子串(字符串一)的字符必须连续出现在字符串二中.请编写一个函数,输入两个字符串,求它们的最长公共子串,并打印出最长公共子串.例如:输入两个字符串BDCABA和ABCBDAB,字符串BCBA和BDAB都是是它们的最长公共子串,则输出它们的长度4,并打印任意一个子串. 分析:求最长公共子串(Longest Common Subsequence, LCS)是一道非常经典的动态规划题,

  • python实现求两个字符串的最长公共子串方法

    如下所示: # coding:utf-8 ''' 求两个字符串的最长公共子串 思想:建立一个二维数组,保存连续位相同与否的状态 ''' def getNumofCommonSubstr(str1, str2): lstr1 = len(str1) lstr2 = len(str2) record = [[0 for i in range(lstr2+1)] for j in range(lstr1+1)] # 多一位 maxNum = 0 # 最长匹配长度 p = 0 # 匹配的起始位 for

  • python 实现求解字符串集的最长公共前缀方法

    问题比较简单,给定一个字符串集合求解其中最长的公共前缀即可,这样的问题有点类似于最长公共子序列的问题,但是比求解最长最长公共子序列简单很多,因为是公共前缀,这样的话只需要挨个遍历即可,只要遍历长度结束或者结束前发现有不相同的即可终止,返回不同位置之前的子序列即可,下面是具体的实现: #!usr/bin/env python #encoding:utf-8 ''' __Author__:沂水寒城 功能:求解字符串集的最长公共前缀 ''' def find_longest_prefix(str_li

  • 详解Python最长公共子串和最长公共子序列的实现

    详解Python最长公共子串和最长公共子序列的实现

    最长公共子串(The Longest Common Substring) LCS问题就是求两个字符串最长公共子串的问题.解法就是用一个矩阵来记录两个字符串中所有位置的两个字符之间的匹配情况,若是匹配则为1,否则为0.然后求出对角线最长的1的序列,其对应的位置就是最长匹配子串的位置. def find_lcsubstr(s1, s2): m=[[0 for i in range(len(s2)+1)] for j in range(len(s1)+1)] #生成0矩阵,为方便后续计算,比字符串长度

  • 利用C++实现最长公共子序列与最长公共子串

    利用C++实现最长公共子序列与最长公共子串

    一.问题描述 子串应该比较好理解,至于什么是子序列,这里给出一个例子:有两个母串 cnblogs belong 比如序列bo, bg, lg在母串cnblogs与belong中都出现过并且出现顺序与母串保持一致,我们将其称为公共子序列.最长公共子序列(Longest Common Subsequence, LCS),顾名思义,是指在所有的子序列中最长的那一个.子串是要求更严格的一种子序列,要求在母串中连续地出现.在上述例子的中,最长公共子序列为blog(cnblogs, belong),最长公共

  • PHP实现求解最长公共子串问题的方法

    本文实例讲述了PHP实现求解最长公共子串问题的方法.分享给大家供大家参考,具体如下: 题目:如果字符串一的所有字符按其在字符串中的顺序出现在另外一个字符串二中,则字符串一称之为字符串二的子串. 注意,并不要求子串(字符串一)的字符必须连续出现在字符串二中.即,可以不连续,但顺序不能变. 请编写一个函数,输入两个字符串,求它们的最长公共子串,并打印出一个最长公共子串. 例如:输入两个字符串BDCABA和ABCBDAB,字符串BCBA和BDAB都是是它们的最长公共子串, 下面的算法是根据网上的jav

  • JavaScript自定义函数实现查找两个字符串最长公共子串的方法

    本文实例讲述了JavaScript自定义函数实现查找两个字符串最长公共子串的方法.分享给大家供大家参考,具体如下: //查找两个字符串的最长公共子串 function findSubStr(s1,s2){ var S=sstr= "" ,L1=s1.length,L2=s2.length; if (L1>L2){ var s3=s1;s1=s2,s2=s3,L1=s2.length;} for ( var j=L1;j> 0 ;j--) for ( var i= 0 ;i&

  • C语言求两个字符串的最长公共子串

    本文实例讲述了C语言求两个字符串的最长公共子串的方法.分享给大家供大家参考.具体实现方法如下: #include "stdio.h" #include "string.h" #include "stdlib.h" void getCommon(char str1[],char str2[],char * str3); int stringLength(char * str); void main(){ char str1[50]; char st

随机推荐