python?動(dòng)態(tài)規(guī)劃問(wèn)題解析(背包問(wèn)題和最長(zhǎng)公共子串)

更新時(shí)間：2022年05月15日 08:29:40 作者：yetangjian

這篇文章主要介紹了python?動(dòng)態(tài)規(guī)劃（背包問(wèn)題和最長(zhǎng)公共子串）,在動(dòng)態(tài)規(guī)劃中，你要將某個(gè)指標(biāo)最大化。在這個(gè)例子中，你要找出兩個(gè)單詞的最長(zhǎng)公共子串。fish和fosh都包含的最長(zhǎng)子串是什么呢,感興趣的朋友跟隨小編一起看看吧

背包問(wèn)題

現(xiàn)在要往一個(gè)可以裝4個(gè)單位重量的背包里怎么裝價(jià)值最高：A重量1個(gè)單位，價(jià)值15；B重量3個(gè)單位，價(jià)值20；C重量4個(gè)重量，價(jià)值30

使用動(dòng)態(tài)規(guī)劃填充空格

class SolutionBag:
    def valuableBag(self,optionalList,sizeBig):
        #創(chuàng)建網(wǎng)格
        grid = [[0 for i in range(sizeBig+1)] for j in range(len(optionalList)+1)]
        #從行列序號(hào)1開始計(jì)數(shù)
        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)

最長(zhǎng)公共子串

在動(dòng)態(tài)規(guī)劃中，你要將某個(gè)指標(biāo)最大化。在這個(gè)例子中，你要找出兩個(gè)單詞的最長(zhǎng)公共子串。fish和fosh都包含的最長(zhǎng)子串是什么呢

如何將這個(gè)問(wèn)題劃分為子問(wèn)題呢？你可能需要比較子串：不是比較hish和fish，而是先比較his和fis

我們網(wǎng)格填充的方法來(lái)實(shí)現(xiàn)

#偽代碼
#字母相同則左上方+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實(shí)現(xiàn)網(wǎng)格

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

到此這篇關(guān)于python 動(dòng)態(tài)規(guī)劃（背包問(wèn)題和最長(zhǎng)公共子串）的文章就介紹到這了,更多相關(guān)python 動(dòng)態(tài)規(guī)劃內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: