Python动态规划中问题如何解决，用示例怎样说明-群英

上一篇：详解Python中六个很实用的内置函数的用法下一篇：如何用Python+OpenCV做多种炫酷的图像特效

这篇文章给大家介绍了“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动态规划中问题如何解决，用示例怎样说明内容，欢迎关注群英网络技术资讯频道，小编将为大家输出更多高质量的实用文章！