Day3

• Day3-part1
• • 問(wèn)題描述
  • 公共子序列解決思路
  • • 遞推公式的確定
  • 獲取序列信息
• Day3-part2
• • 問(wèn)題描述
  • 0/1背包解決思路
  • 找到具體放入的物品
  • 一種可行的解決方案

Day3-part1

Longest Common Subsequence 最長(zhǎng)公共子序列問(wèn)題

問(wèn)題描述

這里主要想解決的問(wèn)題是，確定兩個(gè)字符串所包含的公共序列，允許字符之間存在間隙，但是不允許改變字符之間的順序，例如：
序列1： GATTACA
序列2： TACTGTC
最長(zhǎng)公共子序列顯然為： ATTC， 但是如何確定公共子序列最大長(zhǎng)度，以及具體是什么呢？

公共子序列解決思路

[1 ] 確定dp數(shù)組（dp table）以及下標(biāo)的含義
[2 ] 確定遞推公式
[3 ] dp數(shù)組如何初始化
[4 ] 確定遍歷順序
[5 ] 舉例推導(dǎo)dp數(shù)組

我們解決這個(gè)問(wèn)題，如果分別從兩個(gè)序列的頭部向后看，比如現(xiàn)在：
S_source=GATTACA
S_target=TACTGTC
從target第一個(gè)元素開(kāi)始看起

GATTACT
TAC
此時(shí)LCS=3，因?yàn)镾_target后續(xù)元素T，在source中找不到了，最大的長(zhǎng)度就為3！

同理，如果反過(guò)來(lái)看呢：

TACTGTC
GATTACA
此時(shí)LCS=3，因?yàn)楹罄m(xù)元素找不到了，最大的長(zhǎng)度就為3！

因此，很自然我們可以想到，想獲取最長(zhǎng)公共子序列，需要兩個(gè)字符串序列，分別去對(duì)方的序列中尋找，那么dp數(shù)組應(yīng)該是一個(gè)二維數(shù)組。dp數(shù)組每個(gè)位置的含義是什么呢？
dp[i][j] 對(duì)應(yīng)的是 S_target[0:j] 在序列 S_source[0:i] 中， 兩者對(duì)應(yīng)的最大公共子序列。
比如： dp[0][5]對(duì)應(yīng)的是 ‘G’ 在序列 ‘TACTGT’ 中的公共子序列長(zhǎng)度， 顯然為1
比如： dp[3][5]對(duì)應(yīng)的是 ‘GATT’ 在序列 ‘TACTGT’ 中的公共子序列長(zhǎng)度， 顯然為3

s_source='GATTACA' s_target='TACTGTC' dp=[[0 for i in range(len(s_target))] for j in range(len(s_source))]

下圖為對(duì)應(yīng)生成的二維數(shù)組，并且全部由0充滿

那么，我們應(yīng)該對(duì)dp數(shù)組進(jìn)行初始化。根據(jù)如上的分析，很容易對(duì)第一行和第一列進(jìn)行初始化

for i in range(len(s_target)):if s_source[0]==s_target[i]:for j in range(i,len(s_traget)):result[0][j]=1break for i in range(len(s_source)):if s_target[0]==s_source[i]:for j in range(i,len(s_source)):result[j][0]=1break

遞推公式的確定

動(dòng)態(tài)規(guī)劃的核心是確定遞推公式，針對(duì)很多問(wèn)題應(yīng)該首先確定遞推公式，隨后確定dp數(shù)組初始化，但是在這里的話，為了針對(duì)分析的便利顯示，我們首先將圖繪出，進(jìn)行分析。
針對(duì)問(wèn)號(hào)點(diǎn)的數(shù)值我們應(yīng)該如何確定呢？

針對(duì)點(diǎn)dp[ i ] [ j ]，如果滿足s_source[ i ] == s_target[ j ]的話，那公共子序列的長(zhǎng)度肯定就會(huì)+1
是針對(duì)誰(shuí)+1呢？ 顯然是針對(duì)dp[ i-1 ] [ j-1 ]的數(shù)值+1， 即針對(duì)上一個(gè)狀態(tài)+1
if s_source[ i ] == s_target[ j ] → dp[ i ] [ j ]=dp[ i-1 ] [ j-1 ]+1
當(dāng)時(shí)當(dāng) s_source[ i ] ！= s_target[ j ]，現(xiàn)在應(yīng)該執(zhí)行什么操作呢？
想一想~
那現(xiàn)在肯定不能是前一個(gè)狀態(tài)+1了，甚至說(shuō)，都不應(yīng)該考慮+1的事情了！
但是現(xiàn)在還是想知道公共子序列的最長(zhǎng)長(zhǎng)度，那么現(xiàn)在dp[ i ] [ j ] 應(yīng)該就是對(duì)應(yīng)未進(jìn)入i，j狀態(tài)的最大值了！
dp[ i ] [ j ] =max（dp[ i-1 ] [ j ]，dp[ i ] [ j-1 ]）
if s_source[ i ] ！= s_target[ j ] → dp[ i ] [ j ]=max（dp[ i-1 ] [ j ]，dp[ i ] [ j-1 ]）

for i in range(1,len(s_source)):for j in range(1,len(s_target)):if s_source[i]==s_target[j]:dp[i][j]=dp[i-1][j-1]+1else:dp[i][j]=max(dp[i-1][j],dp[i][j-1])

至此，可以獲得完全的dp矩陣，最大子序列長(zhǎng)度應(yīng)當(dāng)出現(xiàn)在dp[ len(s_source)-1 ][ len(s_target)-1 ]
即右下角的點(diǎn)的值！

獲取序列信息

如何獲得子序列信息分別是什么呢？
需要進(jìn)行的操作是從右下角開(kāi)始尋找，逐步往上或者往左移動(dòng)，標(biāo)記dp[ i ][ j ] >dp[ i-1 ][ j ] 同時(shí)dp[ i ][ j ] >dp[ i ][ j-1 ]的點(diǎn)，對(duì)應(yīng)的字符即為我們想知道的子序列

common_string=[] i=len(s_source)-1 j=len(s_target)-1 while(i>=1 and j>=1):if dp[i][j]>dp[i-1][j] and dp[i][j]>dp[i][j-1]:common_string.append((s_source[i]))i-=1j-=1elif dp[i][j]==dp[i-1][j]:i-=1elif dp[i][j]==dp[i][j-1]:j-=1 return common_string

Day3-part2

The 0/1 knapsack Problem 0/1背包問(wèn)題

問(wèn)題描述

你有一個(gè)背包需要填充，背包的體積容量有要求。針對(duì)每個(gè)物品，你只可以選擇0件/1件。每個(gè)物品有自己的體積（重量），和他對(duì)應(yīng)的價(jià)值，現(xiàn)在你要做的事情：合理選擇物品獲得背包最大價(jià)值！
物品（items）：（ wi , valuei ） 物品重量、價(jià)值
（3，9）；（1，7）；（12，18）；（5，3）；（2，11）
背包容量：10 最大價(jià)值：9+7+11=27 選擇物品：3+1+2
窮舉的話，肯定是可以舉出來(lái)的，但是這是否有點(diǎn)太暴力了。
我們?cè)谶@里想一下用動(dòng)態(tài)規(guī)劃怎么來(lái)做呢？

0/1背包解決思路

[1 ] 確定dp數(shù)組（dp table）以及下標(biāo)的含義
[2 ] 確定遞推公式
[3 ] dp數(shù)組如何初始化
[4 ] 確定遍歷順序
[5 ] 舉例推導(dǎo)dp數(shù)組

第一步，確定dp數(shù)組，這里的dp數(shù)組我們首先想到的是，延續(xù)part1的思路，我們構(gòu)建一個(gè)二維數(shù)組。
整個(gè)二維數(shù)組，row=len(items), column=weight+1。
行代表是否放入某個(gè)物品進(jìn)行考慮，列代表針對(duì)不同容量的背包從0容量開(kāi)始考慮。
dp[ i ][ j ] 代表目前情況下背包內(nèi)能放下的最大價(jià)值。

第二步，確定遞推公式。
針對(duì)任意的 i，j。i 代表是否要放入物品 i ，j 代表的是當(dāng)前的背包容量。 很直觀我們想到的是雙重循環(huán)，先遍歷 i 再遍歷 j。針對(duì)dp[ i ][ j ]，肯定要取當(dāng)前能取到的最大值，才能確保背包含有的價(jià)值是最大值。
dp[ i ][ j ]的取值無(wú)非是兩種情況：

• 不放入items[ i ]，那么dp[ i ][ j ]=dp[ i-1 ][ j ] ,也就是說(shuō)和不放入的情況一模一樣嘍！
• 如果放入items[ i ]，那么dp[ i ][ j ]=dp[ i-1 ][ j-items[ i ][ 0 ] ]+items[ i ][ 1 ] (這個(gè)不懂看圖)
  
  現(xiàn)在看我畫圈圈的地方，現(xiàn)在是不是針對(duì)背包容量為5，考慮item（1，7）的情況！
  如果不放入item的話，那么dp[ i ][ j ]=9
  如果放入item的話，那么就相當(dāng)于上一行背包容量為4的時(shí)候的值**（黃色點(diǎn)）**，再加上item（1，7），dp[ i ][ j ]=9+7=16，這兩個(gè)取最大值就是這個(gè)紅色圈圈應(yīng)該放進(jìn)去的值，對(duì)吧！
  dp[ i ][ j ]=max(dp[ i-1 ][ j ], dp[ i-1 ][ j-items[ i ][0]] +items[ i ][ 1 ])

第三步，dp數(shù)組初始化
這一步也很簡(jiǎn)單的對(duì)吧！因?yàn)樽铋_(kāi)始肯定是空空蕩蕩的背包嘍，每個(gè)點(diǎn)的價(jià)值都會(huì)是0！
dp[ i ][ j ]=0，千真萬(wàn)確。

第四步，確定遍歷順序
遍歷順序：先行后列，前面有說(shuō)過(guò)，那么現(xiàn)在通過(guò)我們的代碼實(shí)現(xiàn)吧！

value=[[3,9],[1,7],[12,18],[5,3],[2,11] ] #前項(xiàng)代表重量，后項(xiàng)代表價(jià)值 def get_max_value(weight):dp=[[0 for i in range(weight+1)] for j in range(len(value)+1)]for i in range(1,len(value)+1):for j in range(1,weight+1):if j >=value[i-1][0]:dp[i][j]=max(dp[i-1][j],dp[i][j-value[i-1][0]]+value[i-1][1])else:dp[i][j]=dp[i-1][j]return dp[len(value)][weight]

def get_max_value(weight):dp=[[0 for i in range(weight+1)]for j in range(len(value))]for i in range(value[0][0],weight+1):dp[0][i]=value[0][1]for i in range(1,len(value)):for j in range(0,weight+1):if j>=value[i][0]:dp[i][j]=max(dp[i-1][j],dp[i-1][j-value[i][0]]+value[i][1])else:dp[i][j]=dp[i-1][j]return dp[len(value)-1][weight]

這就是執(zhí)行完的樣子了，右下角就是最大價(jià)值了，自己動(dòng)手實(shí)現(xiàn)一下吧！

找到具體放入的物品

那么，我們?cè)趺床拍苤?strong>具體放入了什么物品呢？

因?yàn)樵赿p數(shù)組中，最后一列代表著背包容量為weight的最大價(jià)值，那么在這里對(duì)最后一列進(jìn)行分析。

27-16=11 篩選出item(2,11)
16-9=7 篩選出item（1,7）
9-0=9 篩選出item(3,9)
最終得到結(jié)果 item（2，1，3）

這里理解怎么出來(lái)的就好，基本上不會(huì)讓你去實(shí)現(xiàn)的，fine！
現(xiàn)在pdf上面的內(nèi)容就實(shí)現(xiàn)完了！Day3你已經(jīng)成功拿下了！

一種可行的解決方案

現(xiàn)在我們的dp數(shù)組是一個(gè)二維數(shù)組對(duì)吧！這肯定會(huì)占用很大的存儲(chǔ)空間，我們用一維數(shù)組能不能處理這個(gè)事情呢，可以的，是可以的。

數(shù)組遞推方法：

dp[ i ]=max(dp[ i ],dp[ i-items[ i ][ 0 ] ]+items[ i ][ 1 ] )
還是考慮兩種情況，是否放入items[i]
如果不放入： dp[ i ]=dp[ i ]
如果放入： dp[ i ]=dp[ i-items[ i ][ 0 ] ]+items[ i ][ 1 ] 想一下為什么呢？其實(shí)和二維是一樣的，就是預(yù)留容量?jī)r(jià)值 + 物品價(jià)值！
兩者取最大值是不是就完事了！

數(shù)組初始化：
初始均為0

def max_value(weight):dp=[0]*(weight+1)for i in range(len(value)):for j in range(weight,value[i][0]-1,-1):dp[j]=max(dp[j],dp[j-value[i][0]]+value[i][1])return dp[weight]

注意仔細(xì)閱讀兩層循環(huán)嵌套，第二層循環(huán)嵌套，是不是逆向進(jìn)行的？ 為什么要逆向呢？
自己想一下，如果是正向的話，如果重量滿足情況，在不斷更新中，是不是將這個(gè)物體重復(fù)放入了，這樣就不是 0/1背包 問(wèn)題了！

自己動(dòng)手實(shí)現(xiàn)吧，辛苦了！

?？驼勫?#xff0c;煙濤微茫信難求。

越人語(yǔ)天姥，云霞明滅或可睹。

天姥連天向天橫，勢(shì)拔五岳掩赤城。

天臺(tái)一萬(wàn)八千丈，對(duì)此欲倒東南傾。

我欲因之夢(mèng)吳越，一夜飛度鏡湖月。

總結(jié)

以上是生活随笔為你收集整理的Python Prep随想练习-Day3的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。