當(dāng)前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

灯神动态规划(Dynamic Programing)学习笔记打劫问题凑整问题背包问题例题+原理+源码超详细讲解

發(fā)布時間：2023/12/16 编程问答 22 豆豆

生活随笔收集整理的這篇文章主要介紹了灯神动态规划(Dynamic Programing)学习笔记打劫问题凑整问题背包问题例题+原理+源码超详细讲解小編覺得挺不錯的,現(xiàn)在分享給大家,幫大家做個參考.

動態(tài)規(guī)劃Dynamic Programing學(xué)習(xí)筆記打劫問題湊整問題背包問題

學(xué)習(xí)資源
- Example1. 打家劫舍問題 looting problem
- Example2. 湊整問題
Example3. 背包問題

學(xué)習(xí)資源

燈神的視頻是我目前個人覺得講解最清晰的動態(tài)規(guī)劃教學(xué)，這篇文章是對他視頻內(nèi)容的匯總，在此基礎(chǔ)上我還個人補充了背包問題的解決方案。
燈神的b站小課堂

Example1. 打家劫舍問題 looting problem

題目模型簡化如下：給定數(shù)組arr=[4,1,1,9,1]，從中選擇數(shù)字來使得總和最大，注意不能選擇相鄰的數(shù)字。例如，選擇4后，不能選擇1；選擇9后，不能選擇9左右兩側(cè)的數(shù)字1。

模型建立。我們拿出一組新的數(shù)組arr=[1,2,4,1,7,8,3]，將其按順序分別編號為0-6。如圖

假定opt(6)表示：從前6個數(shù)字中選出總和最大的最佳方案（也就是我們期望得到的結(jié)果），同理opt(5)表示從前五個數(shù)字中選出來總和最大的方案……依次類推。

我們在這個基礎(chǔ)上進(jìn)行推理：對于第六個數(shù)字，我們有選擇和不選擇這兩種操作，當(dāng)我們選擇第六個數(shù)時，根據(jù)規(guī)則就無法選擇第五個數(shù)字，因此opt(6)=opt(4)+arr[6],即在這種情況下，opt6的值等于前四個數(shù)字中選出的最大值加上第六個數(shù)的數(shù)值。如果我們不選擇第六個數(shù)，那么opt(6)=opt(5)，即前五個數(shù)所能選出總和最大的值。

根據(jù)這個邏輯，為了算出opt6，我們需要經(jīng)歷以下過程。加號表示選擇當(dāng)前數(shù)，減號表示不選擇當(dāng)前數(shù)。整個過程的樹狀圖如下根據(jù)上圖所示的邏輯，我們可以從中推出普遍的遞推規(guī)律。因為我們是求最大值，所以前i個數(shù)字所能構(gòu)成的最大總和為opt(i)=max(opt(i-1),opt(i-2)+arr[i])，其中，opt(i)是我們放棄選擇第i個數(shù)時所得到的前i-1個數(shù)能構(gòu)成的最大值；opt(i-2)+arr[i] 是我們選擇第i個數(shù)時能得到的最大值。

尋找出口條件：#當(dāng)i=0時 opt(1)=max(arr[1],arr[0]) #當(dāng)i=1時 opt(0)=arr(0)

用代碼來實現(xiàn)當(dāng)前邏輯。分兩種，首先是recursive method

import numpy as nparr=[1,2,4,1,7,8,3]def rec_method(arr,i): #recursive methodif i==0: #在if和elif中填寫我們前面推出來的出口條件return arr[0]elif i==1:return max(arr[0],arr[1])else: #在else中填寫我們發(fā)現(xiàn)的基本邏輯a=rec_method(arr,i-1)b=rec_method(arr,i-2)+arr[i]return max(a,b)rec_method(arr,6)

運行這段代碼后可以發(fā)現(xiàn)最終結(jié)果為15。這個地方我們運行的基本原理就是在函數(shù)中不停地調(diào)用自身，最終由opt6出發(fā)推演至opt0，直到算出答案（如上面我手繪的樹狀圖）。這種辦法雖然變成起來思路比較直觀，但在該推演過程中有很多重復(fù)的運算。回到上面的樹狀圖，該辦法在計算opt6時，重復(fù)計算了opt4和opt3，我分別用黃色、綠色熒光筆將重復(fù)部分標(biāo)記了起來。

當(dāng)arr內(nèi)數(shù)據(jù)和i的數(shù)量變大時，使用這種辦法的運算成本將大幅升高。接下來介紹非recursive的計算方法：

#續(xù)上面的代碼 def nonrec_method(arr):opt = np.zeros(len(arr)) #建立數(shù)組來存儲opt數(shù)據(jù)opt[0]=arr[0]opt[1]=max(arr[1],arr[0])for i in range(2,len(arr)):A = opt[i-2]+arr[i]B = opt[i-1]opt[i] = max(A,B)return opt[len(arr)-1] nonrec_method(arr)

輸出結(jié)果為15.0。該種方法可以理解為逆著樹狀圖，由opt0出發(fā)一步一步推演至最終結(jié)果opt6，好處在于每一步的結(jié)果我們都儲存在了數(shù)組中，節(jié)約了不少計算資源。

Example2. 湊整問題

題目要求如下，給定數(shù)組arr=[3,34,4,12,5,2],判斷能否實用數(shù)組內(nèi)的數(shù)構(gòu)成S（s為一個數(shù)）。

模型建立：假定S=9，將arr中的數(shù)據(jù)從0-5進(jìn)行編號。如圖

我們設(shè)subset(i,S)，其中i表示使用前i個數(shù)字，S為我們期望拼湊成的數(shù)。例如，subset(5,9)表示使用前五個數(shù)字來拼湊出9的總和。subset(2,3)表示使用前兩個數(shù)字拼湊出3。我們從這個符號出發(fā)，開始推理過程，首先考慮subset(5,9),我們此時要用前五個數(shù)來拼出9，首先判斷第五個數(shù)。在這個地方我們有兩種選擇，第一種選擇是使用第五個數(shù)來拼湊出9，那么選擇后的情況就變成了subset(4,7)，表示用前4個數(shù)去湊成7。第二種選擇是不使用第五個數(shù)，那么情況就變成了subset(4,9)。繪制成樹狀圖如下

由此我們可以推出普遍的遞推規(guī)律，若使用前i個數(shù)湊成S，遞推規(guī)律表達(dá)式為其中arr表示存放數(shù)據(jù)的數(shù)組。

接下來，我們開始尋找出口條件，第一種情況是當(dāng)S下降為0時，說明前面的數(shù)字已經(jīng)完成了拼湊任務(wù)，此時應(yīng)該返回True，表示能夠拼湊出S；第二種情況是當(dāng)i下降為0時，S仍然不為0。i=0說明已經(jīng)引導(dǎo)到了數(shù)組的首位數(shù)，如果此時滿足arr[0]==S,那么說明能夠湊出S，返回True。如果不相等則說明arr中的數(shù)字無法拼成S，返回False。這兩個出口條件總結(jié)如下：

if i==0: return arr[0]==S #如果arr[0]==S，說明能湊成，返回True；反之則返回False elif S==0: return True

通過Recursive的方法編寫的python源碼如下：

import numpy as nparr=[3,34,4,12,5,2]def opt(arr,i,S):if S==0 :return Trueelif i==0:return S==arr[i]elif arr[i]>S:return opt(arr,i-1,S)else:A = opt(arr,i-1,S-arr[i])B = opt(arr,i-1,S)return A or B print(opt(arr,len(arr)-1,1))

運行后結(jié)果為True，說明arr內(nèi)的數(shù)字能夠湊出9。

上面的recursive法雖然解決了這個問題，但由于本質(zhì)是重復(fù)的迭代計算，隨著數(shù)組復(fù)雜度的增加，運算占用資源會大大上升，速度也會明顯變慢。在這樣一情況下，我們使用另一種方法來解決這個問題。

def nonrec_opt(arr,S):subset = np.zeros([len(arr),S+1],dtype=bool)subset[0,:]=Falsesubset[:,0]=Trueif arr[0]<S:subset[0,arr[0]]=Truefor i in range(1,len(arr)):for j in range(1,S+1):if arr[i]>j:subset[i,j] = subset[i-1,j]else:A = subset[i-1,j-arr[i]]B = subset[i-1,j]subset[i,j] = A or Bl,w = subset.shapeprint(subset)return subset[l-1,w-1]print(nonrec_opt(arr,9))

運行后輸出結(jié)果同樣為True，但該方法中，我們使用numpy創(chuàng)建了一個數(shù)組，依次計算并存儲了各個階段中subset的bool值，避免了前面recursive method中出現(xiàn)的重復(fù)計算的問題。本質(zhì)上，這種辦法相當(dāng)于創(chuàng)建了一個如下的bool表格：紅圈就是我們最終想要得到的結(jié)果，即`subset(5,9)

Example3. 背包問題

題目要求，有以下編號為1-4的四件物品，他們各自的體積及其所占據(jù)的空間如下表格所示，現(xiàn)有一個容積為8的背包，如果我們想讓該包中所存放的物品價值最大，應(yīng)該怎么放？

題目分析：在Example2中，我們分析了湊整問題的解決方案，當(dāng)前這個背包問題與湊整問題有相似之處但更為復(fù)雜：一點相似之處在于把物品放入背包，相當(dāng)于是一個條件弱化的湊整問題，不需要恰好相等，只需要保證放入物品的總體積小于背包容積即可。不同之處在于，前一個湊整問題的返回值可為布爾量（即0和1），0表示當(dāng)前方案不可行，1表示可以湊出該數(shù)值；本題中不再單純的返回一個布爾量，而是返回背包內(nèi)物品的總價值，我們?nèi)∽罱K價值最高的方案來當(dāng)作最優(yōu)解。

和Example2一樣的方法，我們首先設(shè)計表格：

表格中橫軸從0開始直至背包體積、縱軸從0開始直至物體總數(shù)量。相應(yīng)地，我們在縱軸的旁表上相應(yīng)物品編號的屬性。其中，我用S，size來表示物體體積、V，value表示物品價值。 首先，我們可以在第一行和第一列全部填上0，因為在背包容積為0和包內(nèi)物品數(shù)量為0的這兩種情況下，包內(nèi)物體的總價值都是恒為0的。接下來，我們看編號為1的這一行，在到橫軸的背包體積達(dá)到2之前，一號物品始終是放不進(jìn)書包的，故opt(1,1)為0（這個地方opt表示：當(dāng)物品數(shù)量為1，背包容量為1時，背包內(nèi)物品的最大總價值 ，后面還會常用到）。當(dāng)背包容積為2時，此時能夠放進(jìn)第一個物品，我們有兩種選擇，放入一號物品或者不放入。此時的opt(1,2)也就等于這兩種選擇中讓包內(nèi)物品價值更大的那個選擇，即opt(1,2)=max( 放入,不放入 )。如果放入，背包體積變?yōu)?-2=0，物品數(shù)量1-1=0，即opt(0,0)再加上第一件物品的價值，opt(0,0)+3。如果不放，說明放棄一號物品，物品數(shù)量-1，背包容積不變，即opt(0,2)。如下圖：

按照同樣的邏輯，我們可以依次將該表格填下去，而每一次決策（選或不選）均取決于哪一種選擇能帶來更高的物品總價值，且總能參考前面已經(jīng)得到的opt值。完成的表格如下，（有時間了再更新）

總結(jié)

以上是生活随笔為你收集整理的灯神动态规划(Dynamic Programing)学习笔记打劫问题凑整问题背包问题例题+原理+源码超详细讲解的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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