礦工挖礦問題

礦工挖礦

問題描述

該問題為了解決在給定金礦和礦工數(shù)量的前提下，能夠獲得最多黃金的挖礦策略。很多算法題其實(shí)就是這個(gè)問題換了一個(gè)情境。

有5個(gè)金礦，每個(gè)金礦黃金儲(chǔ)量不同，需要參與挖掘的工人數(shù)目也不同，假定有10個(gè)工人，每個(gè)金礦要么全挖，要么不挖，不可以拆分，試問，想得到最多的黃金，應(yīng)該選擇挖取哪幾個(gè)金礦。金礦信息如下表。

金礦編號(hào)黃金儲(chǔ)量所需工人數(shù)目

1	400	5
2	500	5
3	200	3
4	300	4
5	350	3

題解思路

如果要使用動(dòng)態(tài)規(guī)劃解題，就要確定動(dòng)態(tài)規(guī)劃的三要素：最優(yōu)子結(jié)構(gòu)、邊界和狀態(tài)轉(zhuǎn)移函數(shù)。

最優(yōu)子結(jié)構(gòu)

解題目標(biāo)是確定10個(gè)工人挖5個(gè)金礦能夠獲得最多的黃金量，該問題可以從10個(gè)工人挖4個(gè)金礦的子問題中遞歸求解。而我們?cè)诮鉀Q10個(gè)工人挖4個(gè)金礦時(shí)，存在兩種選擇，一種是放棄第5個(gè)礦，將10個(gè)工人投入到挖四個(gè)礦中；另一種選擇是決定對(duì)第5個(gè)礦進(jìn)行挖掘，因此需要從這10個(gè)人中抽取3個(gè)人（第5個(gè)礦需要人數(shù)）加入第5個(gè)礦開采，剩余的人處理前4個(gè)礦。因此，最優(yōu)解應(yīng)該是這兩種選擇中獲得黃金數(shù)量較多的那一種。

為了描述方便，設(shè)金礦數(shù)量為$n$，工人個(gè)數(shù)為$w$，第n個(gè)礦的黃金數(shù)量為$G[n?1]$,第n個(gè)礦所需工人為$P(n)$，要想獲得10個(gè)礦工挖掘5個(gè)金礦的最優(yōu)解為$max(F(4,10),F(4,10?P[4])+G[4])$。這就是最優(yōu)子結(jié)構(gòu)。

邊界

對(duì)于第一個(gè)金礦而言，若當(dāng)前的礦工數(shù)量不能達(dá)到金礦的挖掘需要?jiǎng)t只能放棄這個(gè)礦，獲得的黃金數(shù)量為0；若能滿足礦工數(shù)量要求，獲得的黃金數(shù)量為$G[0]$。
因此，邊界可以描述為

• $n=1,w>=P[0]$時(shí)，$F(n,w)=G[0]$
• $n=1,w<P[0]$時(shí)，$F(n,w)=0$

狀態(tài)轉(zhuǎn)移函數(shù)

$$F(n,w)=?\begin{array}{rlr}& 0& (n<=1,w<P[0])\\ & G[0]& (n==1,w>=P[0])\\ & F(n?1,w)& (n>1,w<P[n?1])\\ & max(F(n?1,w),F(n?1,w?P[n?1])+G[n?1])& (n>1,w>=P[n?1])\end{array}$$

到這里，三要素找到了，經(jīng)過(guò)這個(gè)過(guò)程也明白了求解過(guò)程，由底向上計(jì)算，一步步推導(dǎo)可以得到結(jié)果，換句話說(shuō)，n步的解其實(shí)就是第一步的結(jié)果推來(lái)的。

首先，我們可以使用遞歸的方法來(lái)寫，它是自頂而下的。

def gold_mining(n ,w, G, P):if n <= 1 and w < P[0]:return 0if n == 1 and w >= P[0]:return G[0]if n > 1 and w < P[n-1]:return gold_mining(n-1, w, G, P)if n > 1 and w >= P[n-1]:return max(gold_mining(n-1, w, G, P), gold_mining(n-1, w-P[n-1], G, P) + G[n-1])if __name__ == '__main__':G = [400, 500, 200, 300, 350]P = [5, 5, 3, 4, 3]n = 5w = 10print(gold_mining(n, w, G, P))

這個(gè)解法可以求得最優(yōu)解，會(huì)以樹形結(jié)構(gòu)求解子問題，如下圖所示，不難發(fā)現(xiàn)，若金礦有$n$和，工人充足，復(fù)雜度即為$O(2^n)$。

優(yōu)化思路

當(dāng)金礦只有5個(gè)的時(shí)候，問題不是很復(fù)雜，但是當(dāng)金礦數(shù)目增加的時(shí)候，這樣的復(fù)雜度是無(wú)法接受的，直觀上來(lái)看，這種遞歸之所以慢其實(shí)是因?yàn)檫M(jìn)行了如下圖所示的重復(fù)計(jì)算。

事實(shí)上，我們可以通過(guò)維護(hù)DP Table的方式來(lái)存儲(chǔ)最優(yōu)解從而以自下而上的方式求解本題，表格中的dp[i][j]就表示F(n,w)的值，因此我們可以得到如下的代碼。

def gold_mining(n ,w, G, P):dp = [[0] * (w+1) for _ in range(len(G)+1)]for i in range(1, len(G)+1):for j in range(1, w+1):if j < P[i-1]:dp[i][j] = dp[i-1][j]else:dp[i][j] = max(dp[i-1][j], dp[i-1][j-P[i-1]] + G[i-1])return dp[len(G)][w]if __name__ == '__main__':G = [400, 500, 200, 300, 350]P = [5, 5, 3, 4, 3]n = 5w = 10print(gold_mining(n, w, G, P))

上述代碼的時(shí)間復(fù)雜度和空間復(fù)雜度都是$O(nw)$，這比遞歸的性能好了很多。

進(jìn)一步優(yōu)化

上面這段代碼其實(shí)時(shí)間上已經(jīng)沒什么優(yōu)化的空間了，空間上還可以進(jìn)一步優(yōu)化。我們不妨回顧DP表，可以發(fā)現(xiàn)，其實(shí)每一行的結(jié)果值依賴于上一行的10個(gè)結(jié)果。舉個(gè)例子，我們已4個(gè)金礦9個(gè)工人為例，$F(4,9)$來(lái)源于$F(3,5)$和$F(3,9)$，這兩個(gè)結(jié)果顯然在上一行已經(jīng)計(jì)算了。

因此，其實(shí)無(wú)論金礦多少個(gè)，我們也只需要保存一行的數(shù)據(jù)，在下一行計(jì)算時(shí)，從右向左統(tǒng)計(jì)并更新數(shù)據(jù)即可。

優(yōu)化后的代碼如下，可以發(fā)現(xiàn)，空間復(fù)雜度降低到了$O(n)$，這就是本題的最優(yōu)方法了。

def gold_mining(n ,w, G, P):dp = [0] * (w+1)for i in range(1, len(G)+1):for j in range(w, 0, -1):if j >= P[i-1]:dp[j] = max(dp[j], dp[j-P[i-1]] + G[i-1])return dp[w]if __name__ == '__main__':G = [400, 500, 200, 300, 350]P = [5, 5, 3, 4, 3]n = 5w = 10print(gold_mining(n, w, G, P))

補(bǔ)充說(shuō)明

具體代碼可以查看我的Github，歡迎Star或者Fork，參考書《你也能看得懂的Python算法書》，書中略微有一點(diǎn)不合理之處，做了修改。到這里，其實(shí)你已經(jīng)體會(huì)到了動(dòng)態(tài)規(guī)劃的簡(jiǎn)約之美，當(dāng)然，要注意Python是有遞歸深度限制的，如不是必要，建議使用循環(huán)控制。

總結(jié)

以上是生活随笔為你收集整理的动态规划算法-02矿工挖矿问题的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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