python?動態(tài)規(guī)劃問題解析(背包問題和最長公共子串)
背包問題
現(xiàn)在要往一個(gè)可以裝4個(gè)單位重量的背包里怎么裝價(jià)值最高：A重量1個(gè)單位，價(jià)值15；B重量3個(gè)單位，價(jià)值20；C重量4個(gè)重量，價(jià)值30
使用動態(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)]
#從行列序號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)最長公共子串
在動態(tài)規(guī)劃中，你要將某個(gè)指標(biāo)最大化。在這個(gè)例子中，你要找出兩個(gè)單詞的最長公共子串。fish和fosh都包含的最長子串是什么呢
如何將這個(gè)問題劃分為子問題呢？你可能需要比較子串：不是比較hish和fish，而是先比較his和fis
我們網(wǎng)格填充的方法來實(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 動態(tài)規(guī)劃（背包問題和最長公共子串）的文章就介紹到這了,更多相關(guān)python 動態(tài)規(guī)劃內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
利用Python實(shí)現(xiàn)批量下載上市公司財(cái)務(wù)報(bào)表
這篇文章主要為大家介紹了如何利用Python做個(gè)小工具，可以批量把某網(wǎng)站上的上市公司的財(cái)報(bào)下下來。文中的示例代碼講解詳細(xì)，感興趣的可以動手試一試2022-03-03
詳解Python 實(shí)現(xiàn) ZeroMQ 的三種基本工作模式
ZMQ是一個(gè)簡單好用的傳輸層，像框架一樣的一個(gè) socket library，他使得 Socket 編程更加簡單、簡潔和性能更高。 ，這篇文章主要介紹了Python 實(shí)現(xiàn) ZeroMQ 的三種基本工作模式,需要的朋友可以參考下2020-03-03
Tensorflow實(shí)現(xiàn)卷積神經(jīng)網(wǎng)絡(luò)的詳細(xì)代碼
這篇文章主要為大家詳細(xì)介紹了Tensorflow實(shí)現(xiàn)卷積神經(jīng)網(wǎng)絡(luò)的詳細(xì)代碼，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2018-05-05
在本篇文章中小編給大家整理了關(guān)于python開發(fā)前景的知識點(diǎn)及相關(guān)內(nèi)容，有興趣的朋友們可以跟著學(xué)習(xí)參考下。2020-06-06
Python?colorama?彩色打印實(shí)現(xiàn)代碼
這篇文章主要介紹了Python?colorama?彩色打印實(shí)現(xiàn)代碼,將介紹的類為Back,?它實(shí)現(xiàn)了與?Fore?類相同的九個(gè)關(guān)鍵字：BLACK、RED、GREEN、YELLOW、BLUE、MAGENTA、CYAN、WHITE、RESET，感興趣的朋友一起看看吧2022-04-04
Python實(shí)現(xiàn)的多進(jìn)程和多線程功能示例
這篇文章主要介紹了Python實(shí)現(xiàn)的多進(jìn)程和多線程功能,結(jié)合實(shí)例形式分析了Python多線程與多進(jìn)程實(shí)現(xiàn)分布式系統(tǒng)功能相關(guān)操作技巧,需要的朋友可以參考下2018-05-05
python+appium自動化測試之如何控制App的啟動和退出
本文主要介紹了python+appium自動化測試之如何控制App的啟動和退出，文中通過示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2022-02-02
這篇文章主要介紹了Python中的groupby分組功能的實(shí)例代碼，非常不錯(cuò)，具有一定的參考借鑒價(jià)值，需要的朋友參考下吧2018-07-07
Python實(shí)現(xiàn)插入排序和選擇排序的方法
這篇文章主要介紹了Python實(shí)現(xiàn)插入排序和選擇排序的方法,非常不錯(cuò)，具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2019-05-05
這篇文章主要介紹了Python實(shí)現(xiàn)的快速排序算法,結(jié)合實(shí)例形式分析了Python快速排序的原理、實(shí)現(xiàn)方法與相關(guān)操作技巧,需要的朋友可以參考下2017-08-08