標(biāo)題: 通過金礦模型介紹動(dòng)態(tài)規(guī)劃 [打印本頁(yè)]
作者: 51黑tt    時(shí)間: 2016-3-5 20:20
標(biāo)題: 通過金礦模型介紹動(dòng)態(tài)規(guī)劃
01背包測(cè)試數(shù)據(jù).rar (4.12 KB, 下載次數(shù): 5)    

         對(duì)于動(dòng)態(tài)規(guī)劃，每個(gè)剛接觸的人都需要一段時(shí)間來(lái)理解，特別是第一次接觸的時(shí)候總是想不通為什么這種方法可行，這篇文章就是為了幫助大家理解動(dòng)態(tài)規(guī)劃，并通過講解基本的01背包問題來(lái)引導(dǎo)讀者如何去思考動(dòng)態(tài)規(guī)劃。本文力求通俗易懂，無(wú)異性，不讓讀者感到迷惑，引導(dǎo)讀者去思考，所以如果你在閱讀中發(fā)現(xiàn)有不通順的地方，讓你產(chǎn)生錯(cuò)誤理解的地方，讓你難得讀懂的地方，請(qǐng)跟貼指出，謝謝！




----第一節(jié)----初識(shí)動(dòng)態(tài)規(guī)劃--------

       經(jīng)典的01背包問題是這樣的：
       有一個(gè)包和n個(gè)物品，包的容量為m，每個(gè)物品都有各自的體積和價(jià)值，問當(dāng)從這n個(gè)物品中選擇多個(gè)物品放在包里而物品體積總數(shù)不超過包的容量m時(shí)，能夠得到的最大價(jià)值是多少？[對(duì)于每個(gè)物品不可以取多次，最多只能取一次，之所以叫做01背包，0表示不取，1表示取]

       為了用一種生動(dòng)又更形象的方式來(lái)講解此題，我把此題用另一種方式來(lái)描述，如下：
      
       有一個(gè)國(guó)家，所有的國(guó)民都非常老實(shí)憨厚，某天他們?cè)谧约旱膰?guó)家發(fā)現(xiàn)了十座金礦，并且這十座金礦在地圖上排成一條直線，國(guó)王知道這個(gè)消息后非常高興，他希望能夠把這些金子都挖出來(lái)造福國(guó)民，首先他把這些金礦按照在地圖上的位置從西至東進(jìn)行編號(hào)，依次為0、1、2、3、4、5、6、7、8、9，然后他命令他的手下去對(duì)每一座金礦進(jìn)行勘測(cè)，以便知道挖取每一座金礦需要多少人力以及每座金礦能夠挖出多少金子，然后動(dòng)員國(guó)民都來(lái)挖金子。

       題目補(bǔ)充1：挖每一座金礦需要的人數(shù)是固定的，多一個(gè)人少一個(gè)人都不行。國(guó)王知道每個(gè)金礦各需要多少人手，金礦i需要的人數(shù)為peopleNeeded。
       題目補(bǔ)充2：每一座金礦所挖出來(lái)的金子數(shù)是固定的，當(dāng)?shù)趇座金礦有peopleNeeded人去挖的話，就一定能恰好挖出gold個(gè)金子。否則一個(gè)金子都挖不出來(lái)。
       題目補(bǔ)充3：開采一座金礦的人完成開采工作后，他們不會(huì)再次去開采其它金礦，因此一個(gè)人最多只能使用一次。
       題目補(bǔ)充4：國(guó)王在全國(guó)范圍內(nèi)僅招募到了10000名愿意為了國(guó)家去挖金子的人，因此這些人可能不夠把所有的金子都挖出來(lái)，但是國(guó)王希望挖到的金子越多越好。
       題目補(bǔ)充5：這個(gè)國(guó)家的每一個(gè)人都很老實(shí)（包括國(guó)王），不會(huì)私吞任何金子，也不會(huì)弄虛作假，不會(huì)說(shuō)謊話。
       題目補(bǔ)充6：有很多人拿到這個(gè)題后的第一反應(yīng)就是對(duì)每一個(gè)金礦求出平均每個(gè)人能挖出多少金子，然后從高到低進(jìn)行選擇，這里要強(qiáng)調(diào)這種方法是錯(cuò)的，如果你也是這樣想的，請(qǐng)考慮背包模型，當(dāng)有一個(gè)背包的容量為10，共有3個(gè)物品，體積分別是3、3、5，價(jià)值分別是6、6、9，那么你的方法取到的是前兩個(gè)物品，總價(jià)值是12，但明顯最大值是后兩個(gè)物品組成的15。
       題目補(bǔ)充7：我們只需要知道最多可以挖出多少金子即可，而不用關(guān)心哪些金礦挖哪些金礦不挖。

       那么，國(guó)王究竟如何知道在只有10000個(gè)人的情況下最多能挖出多少金子呢？國(guó)王是如何思考這個(gè)問題的呢？

       國(guó)王首先來(lái)到了第9個(gè)金礦的所在地（注意，第9個(gè)就是最后一個(gè)，因?yàn)槭菑?開始編號(hào)的，最西邊的那個(gè)金礦是第0個(gè)），他的臣子告訴他，如果要挖取第9個(gè)金礦的話就需要1500個(gè)人，并且第9個(gè)金礦可以挖出8888個(gè)金子。聽到這里國(guó)王哈哈大笑起來(lái)，因?yàn)樵人詾橐朗畟�(gè)金礦在僅有10000個(gè)人的情況下最多能挖出多少金子是一件很難思考的問題，但是，就在剛才聽完他的臣子所說(shuō)的那句話時(shí)，國(guó)王已經(jīng)知道總共最多能挖出多少金子了，國(guó)王是如何在不了解其它金礦的情況下知道最多能挖出多少金子的呢？他的臣子們也不知道這個(gè)謎，因此他的臣子們就問他了：“最聰明的國(guó)王陛下，我們都沒有告訴您其它金礦的情況，您是如何知道最終答案的呢？”

       得意的國(guó)王笑了笑，然后把他最得意的“左、右手”叫到跟前，說(shuō)到：“我并不需要考慮最終要挖哪些金礦才能得到最多的金子，我只需要考慮我面前的這座金礦就可以了，對(duì)于我面前的這座金礦不外乎僅有兩種選擇，要么挖，要么不挖，對(duì)吧？”

       “當(dāng)然，當(dāng)然”大臣們回答倒。
      
       國(guó)王繼續(xù)說(shuō)道：“如果我挖取第9座金礦的話那么我現(xiàn)在就能獲得8888個(gè)金子，而我將用去1500個(gè)人，那么我還剩下8500個(gè)人。我親愛的左部下，如果你告訴我當(dāng)我把所有剩下的8500個(gè)人和所有剩下的其它金礦都交給你去開采你最多能給我挖出多少金子的話，那么我不就知道了在第9個(gè)金礦一定開采的情況下所能得到的最大金幣數(shù)嗎？”
      
       國(guó)王的左部下聽后回答道：“國(guó)王陛下，您的意思是如果我能用8500個(gè)人在其它金礦最多開采出x個(gè)金幣的話，那您一共就能夠獲得 x + 8888個(gè)金子，對(duì)嗎？”
      
       “是啊，是啊……如果第9座金礦一定開采的話……”大臣們點(diǎn)頭說(shuō)到。
      
       國(guó)王笑著繼續(xù)對(duì)著他的右部下說(shuō)到：“親愛的右部下，也許我并不打算開采這第9座金礦，那么我依然擁有10000個(gè)人，如果我把這10000個(gè)人和剩下的金礦都給你的話，你最多能給我挖出多少個(gè)金子呢？”
      
       國(guó)王的右部下聰明地說(shuō)道：“尊敬的國(guó)王陛下，我明白您的意思了，如果我回答最多能購(gòu)開采出y個(gè)金幣的話，那您就可以在y和x+8888之間選擇一個(gè)較大者，而這個(gè)較大者就是最終我們能獲得的最大金幣數(shù)，您看我這樣理解對(duì)嗎？”
      

       國(guó)王笑得更燦爛了，問他的左部下：“那么親愛的左部下，我給你8500個(gè)人和其余金礦的話你能告訴我最多能挖出多少金子嗎？”

       “請(qǐng)您放心，這個(gè)問題難不倒我”。左部下向國(guó)王打包票說(shuō)到。

       國(guó)王高興地繼續(xù)問他的右部下：“那右部下你呢，如果我給你10000個(gè)人和其余金礦的話你能告訴我最多能挖出多少金子嗎？”

       “當(dāng)然能了！交給我吧！”右部下同左部下一樣自信地回答道。

       “那就拜托給你們兩位了，現(xiàn)在我要回到我那舒適的王宮里去享受了，我期待著你們的答復(fù)�！眹�(guó)王說(shuō)完就開始動(dòng)身回去等消息了，他是多么地相信他的兩個(gè)大臣能夠給他一個(gè)準(zhǔn)確的答復(fù)，因?yàn)閲?guó)王其實(shí)知道他的兩位大臣要比他聰明得多。

       故事發(fā)展到這里，你是否在想國(guó)王的這兩個(gè)大臣又是如何找到讓國(guó)王滿意的答案的呢？他們?yōu)槭裁茨軌蛉绱俗孕拍�？事�?shí)上他們的確比國(guó)王要聰明一些，因?yàn)樗麄儚膰?guó)王的身上學(xué)到了一點(diǎn)，就是這一點(diǎn)讓他們充滿了自信。

       國(guó)王走后，國(guó)王的左、右部下來(lái)到了第8座金礦，早已在那里等待他們的金礦勘測(cè)兵向兩位大臣報(bào)道：“聰明的兩位大臣，您們好，第8座金礦需要1000個(gè)人才能開采，可以獲得7000個(gè)金子”。

       因?yàn)閲?guó)王僅給他的左部下8500個(gè)人，所以國(guó)王的左部下叫來(lái)了兩個(gè)人，對(duì)著其中一個(gè)人問到：“如果我給你7500個(gè)人和除了第8、第9的其它所有金礦的話，你能告訴我你最多能挖出多少金子嗎？”

       然后國(guó)王的左部下繼續(xù)問另一個(gè)人：“如果我給你8500個(gè)人和除了第8、第9的其它所有金礦的話，你能告訴我你最多能挖出多少金子嗎？”

       國(guó)王的左部下在心里想著：“如果他們倆都能回答我的問題的話，那國(guó)王交給我的問題不就解決了嗎？哈哈哈！”

       因?yàn)閲?guó)王給了他的右部下10000個(gè)人，所以國(guó)王的右部下同樣也叫來(lái)了兩個(gè)人，對(duì)著其中一個(gè)人問：“如果我給你9000個(gè)人和除了第8、第9的其它所有金礦的話，你能告訴我你最多能挖出多少金子嗎？”

       然后國(guó)王的右部下繼續(xù)問他叫來(lái)的另一個(gè)人：“如果我給你10000個(gè)人和除了第8、第9的其它所有金礦的話，你能告訴我你最多能挖出多少金子嗎？”

       此時(shí)，國(guó)王的右部下同左部下一樣，他們都在為自己如此聰明而感到滿足。
      
       當(dāng)然，這四個(gè)被叫來(lái)的人同樣自信地回答沒有問題，因?yàn)樗麄兺瑯拥貜倪@兩個(gè)大臣身上學(xué)到了相同的一點(diǎn)，而兩位自認(rèn)為自己一樣很聰明的大臣得意地笑著回到了他們的府邸，等著別人回答他們提出來(lái)的問題，現(xiàn)在你知道了這兩個(gè)大臣是如何解決國(guó)王交待給他們的問題了嗎？

       那么你認(rèn)為被大臣叫去的那四個(gè)人又是怎么完成大臣交給他們的問題的呢？答案當(dāng)然是他們找到了另外八個(gè)人！

       沒用多少功夫，這個(gè)問題已經(jīng)在全國(guó)傳開了，更多人的人找到了更更多的人來(lái)解決這個(gè)問題，而有些人卻不需要去另外找兩個(gè)人幫他，哪些人不需要?jiǎng)e人的幫助就可以回答他們的問題呢？

       很明顯，當(dāng)被問到給你z個(gè)人和僅有第0座金礦時(shí)最多能挖出多少金子時(shí)，就不需要?jiǎng)e人的幫助，因?yàn)槟阒溃绻鹺大于等于挖取第0座金礦所需要的人數(shù)的話，那么挖出來(lái)的最多金子數(shù)就是第0座金礦能夠挖出來(lái)的金子數(shù)，如果這z個(gè)人不夠開采第0座金礦，那么能挖出來(lái)的最多金子數(shù)就是0，因?yàn)檫@唯一的金礦不夠人力去開采。讓我們?yōu)檫@些不需要?jiǎng)e人的幫助就可以準(zhǔn)確地得出答案的人們鼓掌吧，這就是傳說(shuō)中的底層勞動(dòng)人民！

       故事講到這里先暫停一下，我們現(xiàn)在重新來(lái)分析一下這個(gè)故事，讓我們對(duì)動(dòng)態(tài)規(guī)劃有個(gè)理性認(rèn)識(shí)。

       子問題：
       國(guó)王需要根據(jù)兩個(gè)大臣的答案以及第9座金礦的信息才能判斷出最多能夠開采出多少金子。為了解決自己面臨的問題，他需要給別人制造另外兩個(gè)問題，這兩個(gè)問題就是子問題。

       思考動(dòng)態(tài)規(guī)劃的第一點(diǎn)----最優(yōu)子結(jié)構(gòu)：
       國(guó)王相信，只要他的兩個(gè)大臣能夠回答出正確的答案（對(duì)于考慮能夠開采出的金子數(shù)，最多的也就是最優(yōu)的同時(shí)也就是正確的），再加上他的聰明的判斷就一定能得到最終的正確答案。我們把這種子問題最優(yōu)時(shí)母問題通過優(yōu)化選擇后一定最優(yōu)的情況叫做“最優(yōu)子結(jié)構(gòu)”。

       思考動(dòng)態(tài)規(guī)劃的第二點(diǎn)----子問題重疊：
       實(shí)際上國(guó)王也好，大臣也好，所有人面對(duì)的都是同樣的問題，即給你一定數(shù)量的人，給你一定數(shù)量的金礦，讓你求出能夠開采出來(lái)的最多金子數(shù)。我們把這種母問題與子問題本質(zhì)上是同一個(gè)問題的情況稱為“子問題重疊”。然而問題中出現(xiàn)的不同點(diǎn)往往就是被子問題之間傳遞的參數(shù)，比如這里的人數(shù)和金礦數(shù)。
      
       思考動(dòng)態(tài)規(guī)劃的第三點(diǎn)----邊界：
       想想如果不存在前面我們提到的那些底層勞動(dòng)者的話這個(gè)問題能解決嗎？永遠(yuǎn)都不可能！我們把這種子問題在一定時(shí)候就不再需要提出子子問題的情況叫做邊界，沒有邊界就會(huì)出現(xiàn)死循環(huán)。

       思考動(dòng)態(tài)規(guī)劃的第四點(diǎn)----子問題獨(dú)立：
       要知道，當(dāng)國(guó)王的兩個(gè)大臣在思考他們自己的問題時(shí)他們是不會(huì)關(guān)心對(duì)方是如何計(jì)算怎樣開采金礦的，因?yàn)樗麄冎�，�?guó)王只會(huì)選擇兩個(gè)人中的一個(gè)作為最后方案，另一個(gè)人的方案并不會(huì)得到實(shí)施，因此一個(gè)人的決定對(duì)另一個(gè)人的決定是沒有影響的。我們把這種一個(gè)母問題在對(duì)子問題選擇時(shí)，當(dāng)前被選擇的子問題兩兩互不影響的情況叫做“子問題獨(dú)立”。


       這就是動(dòng)態(tài)規(guī)劃，具有“最優(yōu)子結(jié)構(gòu)”、“子問題重疊”、“邊界”和“子問題獨(dú)立”，當(dāng)你發(fā)現(xiàn)你正在思考的問題具備這四個(gè)性質(zhì)的話，那么恭喜你，你基本上已經(jīng)找到了動(dòng)態(tài)規(guī)劃的方法。

       有了上面的這幾點(diǎn)，我們就可以寫出動(dòng)態(tài)規(guī)劃的轉(zhuǎn)移方程式，現(xiàn)在我們來(lái)寫出對(duì)應(yīng)這個(gè)問題的方程式，如果用gold[mineNum]表示第mineNum個(gè)金礦能夠挖出的金子數(shù)，用peopleNeeded[mineNum]表示挖第mineNum個(gè)金礦需要的人數(shù)，用函數(shù)f(people,mineNum)表示當(dāng)有people個(gè)人和編號(hào)為0、1、2、3、……、mineNum的金礦時(shí)能夠得到的最大金子數(shù)的話，f(people,mineNum)等于什么呢？或者說(shuō)f(people,mineNum)的轉(zhuǎn)移方程是怎樣的呢？

       答案是：
當(dāng)mineNum = 0且people >= peopleNeeded[mineNum]時(shí) f(people,mineNum) = gold[mineNum]       當(dāng)mineNum = 0且people < peopleNeeded[mineNum]時(shí) f(people,mineNum) = 0
       當(dāng)mineNum != 0時(shí) f(people,mineNum) = f(people-peopleNeeded[mineNum], mineNum-1) + gold[mineNum]與f(people, mineNum-1)中的較大者，前兩個(gè)式子對(duì)應(yīng)動(dòng)態(tài)規(guī)劃的“邊界”，后一個(gè)式子對(duì)應(yīng)動(dòng)態(tài)規(guī)劃的“最優(yōu)子結(jié)構(gòu)”請(qǐng)讀者弄明白后再繼續(xù)往下看。






----第二節(jié)----動(dòng)態(tài)規(guī)劃的優(yōu)點(diǎn)--------
      
       現(xiàn)在我假設(shè)讀者你已經(jīng)搞清楚了為什么動(dòng)態(tài)規(guī)劃是正確的方法，但是我們?yōu)槭裁葱枰褂脛?dòng)態(tài)規(guī)劃呢？請(qǐng)先繼續(xù)欣賞這個(gè)故事：

       國(guó)王得知他的兩個(gè)手下使用了和他相同的方法去解決交代給他們的問題后，不但沒有認(rèn)為他的兩個(gè)大臣在偷懶，反而很高興，因?yàn)樗溃拇蟪急厝粫?huì)找更多的人一起解決這個(gè)問題，而更多的人會(huì)找更更多的人，這樣他這個(gè)聰明的方法就會(huì)在不經(jīng)意間流傳開來(lái)，而全國(guó)人民都會(huì)知道這個(gè)聰明的方法是他們偉大的國(guó)王想出來(lái)的，你說(shuō)國(guó)王能不高興嗎？

       但是國(guó)王也有一些擔(dān)憂，因?yàn)樗麑?shí)在不知道這個(gè)“工程”要?jiǎng)佑玫蕉嗌偃藖?lái)完成，如果幫助他解決這個(gè)問題的人太多的話那么就太勞民傷財(cái)了。“會(huì)不會(huì)影響到今年的收成呢？”國(guó)王在心里想著這個(gè)問題，于是他請(qǐng)來(lái)了整個(gè)國(guó)家里唯一的兩個(gè)數(shù)學(xué)天才，一個(gè)叫做小天，另一個(gè)叫做小才。

       國(guó)王問小天：“小天啊，我發(fā)覺這個(gè)問題有點(diǎn)嚴(yán)重，我知道其實(shí)這可以簡(jiǎn)單的看成一個(gè)組合問題，也就是從十個(gè)金礦中選取若干個(gè)金礦進(jìn)行開采，看看哪種組合得到的金子最多，也許用組合方法會(huì)更好一些。你能告訴我一共有多少種組合情況嗎？”

       “國(guó)王陛下，如果用組合方法的話一共要考慮2的10次方種情況，也就是1024種情況�！毙√焖伎剂艘粫�(huì)回答到。

       “嗯……，如果每一種情況我交給一個(gè)人去計(jì)算能得到的金子數(shù)的話，那我也要1024個(gè)人，其實(shí)還是挺多的�！眹�(guó)王好像再次感覺到了自己的方法是正確的。

       國(guó)王心理期待著小才能夠給它一個(gè)更好的答案，問到：“小才啊，那么你能告訴我用我的那個(gè)方法總共需要多少人嗎？其實(shí)，我也計(jì)算過，好像需要的人數(shù)是1+2+4+8+16+32+64+……，畢竟每一個(gè)人的確都需要找另外兩個(gè)人來(lái)幫助他們……”

       不辜負(fù)國(guó)王的期待，小才微笑著說(shuō)到：“親愛的國(guó)王陛下，其實(shí)我們并不需要那么多人，因?yàn)橛泻芏鄦栴}其實(shí)是相同的，而我們只需要為每一個(gè)不同的問題使用一個(gè)人力便可�！�

       國(guó)王高興的問到：“此話如何講？”

       “打個(gè)比方，如果有一個(gè)人需要知道1000個(gè)人和3個(gè)金礦可以開采出多少金子，同時(shí)另一個(gè)人也需要知道1000個(gè)人和3個(gè)金礦可以開采出多少金子的話，那么他們可以去詢問相同的一個(gè)人，而不用各自找不同的人浪費(fèi)人力了�！�
      
       國(guó)王思考著說(shuō)到：“嗯，很有道理，如果問題是一樣的話那么就不需要去詢問兩個(gè)不同的人了，也就是說(shuō)一個(gè)不同的問題僅需要一個(gè)人力，那么一共有多少個(gè)不同的問題呢？”   

       “因?yàn)槊總�(gè)問題的人數(shù)可以從0取到10000，而金礦數(shù)可以從0取到10，所以最多大約有10000 * 10 等于100000個(gè)不同的問題�！� 小才一邊算著一邊回答。

       “什么？十萬(wàn)個(gè)問題？十萬(wàn)個(gè)人力？”國(guó)王有點(diǎn)失望。

       “請(qǐng)國(guó)王放心，事實(shí)上我們需要的人力遠(yuǎn)遠(yuǎn)小于這個(gè)數(shù)的，因?yàn)椴皇敲恳粋�(gè)問題都會(huì)遇到，也許我們僅需要一、兩百個(gè)人力就可以解決這個(gè)問題了，這主要和各個(gè)金礦所需要的人數(shù)有關(guān)�！� 小才立刻回答到。

       故事的最后，自然是國(guó)王再一次向他的臣民們證明了他是這個(gè)國(guó)家里最聰明的人，現(xiàn)在我們通過故事的第二部分來(lái)考慮動(dòng)態(tài)規(guī)劃的另外兩個(gè)思考點(diǎn)。

       思考動(dòng)態(tài)規(guī)劃的第五點(diǎn)----做備忘錄：
       正如上面所說(shuō)的一樣，當(dāng)我們遇到相同的問題時(shí)，我們可以問同一個(gè)人。講的通俗一點(diǎn)就是，我們可以把問題的解放在一個(gè)變量中，如果再次遇到這個(gè)問題就直接從變量中獲得答案，因此每一個(gè)問題僅會(huì)計(jì)算一遍，如果不做備忘的話，動(dòng)態(tài)規(guī)劃就沒有任何優(yōu)勢(shì)可言了。              

       思考動(dòng)態(tài)規(guī)劃的第六點(diǎn)----時(shí)間分析：
       正如上面所說(shuō)，如果我們用窮舉的方法，至少需要2^n個(gè)常數(shù)時(shí)間，因?yàn)榭偣灿?^n種情況需要考慮，如果在背包問題中，包的容量為1000，物品數(shù)為100，那么需要考慮2^100種情況,這個(gè)數(shù)大約為10的30次方。

       而如果用動(dòng)態(tài)規(guī)劃，最多大概只有1000*100 = 100000個(gè)不同的問題，這和10的30次方比起來(lái)優(yōu)勢(shì)是很明顯的。而實(shí)際情況并不會(huì)出現(xiàn)那么多不同的問題，比如在金礦模型中，如果所有的金礦所需人口都是1000個(gè)人，那么問題總數(shù)大約只有100個(gè)。

       非正式地，我們可以很容易得到動(dòng)態(tài)規(guī)劃所需時(shí)間，如果共有questionCount個(gè)相同的子問題，而每一個(gè)問題需要面對(duì)chooseCount種選擇時(shí)，我們所需時(shí)間就為questionCount * chooseCount個(gè)常數(shù)。在金礦模型中，子問題最多有大概people * n 個(gè)(其中people是用于開采金礦的總?cè)藬?shù)，n是金礦的總數(shù))，因此questionCount = people * n，而就像國(guó)王需要考慮是采用左部下的結(jié)果還是采用右部下的結(jié)果一樣，每個(gè)問題面對(duì)兩個(gè)選擇，因此chooseCount = 2,所以程序運(yùn)行時(shí)間為 T = O(questionCount * chooseCount) =O(people * n)，別忘了實(shí)際上需要的時(shí)間小于這個(gè)值，根據(jù)所遇到的具體情況有所不同。

       這就是動(dòng)態(tài)規(guī)劃的魔力，它減少了大量的計(jì)算，因此我們需要?jiǎng)討B(tài)規(guī)劃！

                     


      

----第三節(jié)----動(dòng)態(tài)規(guī)劃的思考角度----------
      
       那么什么是動(dòng)態(tài)規(guī)劃呢？我個(gè)人覺得，如果一個(gè)解決問題的方法滿足上面六個(gè)思考點(diǎn)中的前四個(gè)，那么這個(gè)方法就屬于動(dòng)態(tài)規(guī)劃。而在思考動(dòng)態(tài)規(guī)劃方法時(shí)，后兩點(diǎn)同樣也是需要考慮的。

       面對(duì)問題要尋找動(dòng)態(tài)規(guī)劃的方法，首先要清楚一點(diǎn)，動(dòng)態(tài)規(guī)劃不是算法，它是一種方法，它是在一件事情發(fā)生的過程中尋找最優(yōu)值的方法，因此，我們需要對(duì)這件事情所發(fā)生的過程進(jìn)行考慮。而通常我們從過程的最后一步開始考慮，而不是先考慮過程的開始。

       打個(gè)比方，上面的挖金礦問題，我們可以認(rèn)為整個(gè)開采過程是從西至東進(jìn)行開采的（也就是從第0座開始），那么總有面對(duì)最后一座金礦的時(shí)候（第9座），對(duì)這座金礦不外乎兩個(gè)選擇，開采與不開采，在最后一步確定時(shí)再去確定倒數(shù)第二步，直到考慮第0座金礦（過程的開始）。

       而過程的開始，也就是考慮的最后一步，就是邊界。

       因此在遇到一個(gè)問題想用動(dòng)態(tài)規(guī)劃的方法去解決時(shí)，不妨先思考一下這個(gè)過程是怎樣的，然后考慮過程的最后一步是如何選擇的，通常我們需要自己去構(gòu)造一個(gè)過程，比如后面的練習(xí)。







----第四節(jié)----總結(jié)-------

       那么遇到問題如何用動(dòng)態(tài)規(guī)劃去解決呢？根據(jù)上面的分析我們可以按照下面的步驟去考慮：

       1、構(gòu)造問題所對(duì)應(yīng)的過程。
       2、思考過程的最后一個(gè)步驟，看看有哪些選擇情況。
       3、找到最后一步的子問題，確保符合“子問題重疊”，把子問題中不相同的地方設(shè)置為參數(shù)。
       4、使得子問題符合“最優(yōu)子結(jié)構(gòu)”。
       5、找到邊界，考慮邊界的各種處理方式。
       6、確保滿足“子問題獨(dú)立”，一般而言，如果我們是在多個(gè)子問題中選擇一個(gè)作為實(shí)施方案，而不會(huì)同時(shí)實(shí)施多個(gè)方案，那么子問題就是獨(dú)立的。
       7、考慮如何做備忘錄。
       8、分析所需時(shí)間是否滿足要求。
       9、寫出轉(zhuǎn)移方程式。
      




----第五節(jié)----練習(xí)-------

       題目一：買書
       有一書店引進(jìn)了一套書，共有3卷，每卷書定價(jià)是60元，書店為了搞促銷，推出一個(gè)活動(dòng)，活動(dòng)如下：
      
       如果單獨(dú)購(gòu)買其中一卷，那么可以打9.5折。
       如果同時(shí)購(gòu)買兩卷不同的，那么可以打9折。
       如果同時(shí)購(gòu)買三卷不同的，那么可以打8.5折。
      
       如果小明希望購(gòu)買第1卷x本，第2卷y本，第3卷z本，那么至少需要多少錢呢？（x、y、z為三個(gè)已知整數(shù)）。

       當(dāng)然，這道題完全可以不用動(dòng)態(tài)規(guī)劃來(lái)解，但是現(xiàn)在我們是要學(xué)習(xí)動(dòng)態(tài)規(guī)劃，因此請(qǐng)想想如何用動(dòng)態(tài)規(guī)劃來(lái)做？

       答案：

       1、過程為一次一次的購(gòu)買，每一次購(gòu)買也許只買一本（這有三種方案），或者買兩本（這也有三種方案），或者三本一起買（這有一種方案），最后直到買完所有需要的書。
       2、最后一步我必然會(huì)在7種購(gòu)買方案中選擇一種，因此我要在7種購(gòu)買方案中選擇一個(gè)最佳情況。
       3、子問題是，我選擇了某個(gè)方案后，如何使得購(gòu)買剩余的書能用最少的錢？并且這個(gè)選擇不會(huì)使得剩余的書為負(fù)數(shù)。母問題和子問題都是給定三卷書的購(gòu)買量，求最少需要用的錢，所以有“子問題重疊”，問題中三個(gè)購(gòu)買量設(shè)置為參數(shù)，分別為i、j、k。
       4、的確符合。
       5、邊界是一次購(gòu)買就可以買完所有的書，處理方式請(qǐng)讀者自己考慮。
       6、每次選擇最多有7種方案，并且不會(huì)同時(shí)實(shí)施其中多種，因此方案的選擇互不影響，所以有“子問題獨(dú)立”。
       7、我可以用minMoney[j][k]來(lái)保存購(gòu)買第1卷i本，第2卷j本，第3卷k本時(shí)所需的最少金錢。
       8、共有x * y * z 個(gè)問題，每個(gè)問題面對(duì)7種選擇，時(shí)間為：O( x * y * z * 7) =  O( x * y * z )。
       9、用函數(shù)MinMoney(i,j,k)來(lái)表示購(gòu)買第1卷i本，第2卷j本，第3卷k本時(shí)所需的最少金錢，那么有：
              MinMoney(i,j,k)=min(s1,s2,s3,s4,s5,s6,s7),其中s1,s2,s3,s4,s5,s6,s7分別為對(duì)應(yīng)的7種方案使用的最少金錢：
              s1 = 60 * 0.95 + MinMoney(i-1,j,k)
              s2 = 60 * 0.95 + MinMoney(i,j-1,k)
              s3 = 60 * 0.95 + MinMoney(i,j,k-1)
              s4 = (60 + 60) * 0.9 + MinMoney(i-1,j-1,k)
              s5 = (60 + 60) * 0.9 + MinMoney(i-1,j,k-1)
              s6 = (60 + 60) * 0.9 + MinMoney(i-1,j,k-1)
              s7 = (60 + 60 + 60) * 0.85 + MinMoney(i-1,j-1,k-1)

      
      


----第六節(jié)----代碼參考------


       下面提供金礦問題的程序源代碼幫助讀者理解，并提供測(cè)試數(shù)據(jù)給大家練習(xí)。

       輸入文件名為“beibao.in”，因?yàn)檫@個(gè)問題實(shí)際上就是背包問題，所以測(cè)試數(shù)據(jù)文件名就保留原名吧。
       輸入文件第一行有兩個(gè)數(shù)，第一個(gè)是國(guó)王可用用來(lái)開采金礦的總?cè)藬?shù)，第二個(gè)是總共發(fā)現(xiàn)的金礦數(shù)。
       輸入文件的第2至n+1行每行有兩個(gè)數(shù)，第i行的兩個(gè)數(shù)分別表示第i-1個(gè)金礦需要的人數(shù)和可以得到的金子數(shù)。

       輸出文件僅一個(gè)整數(shù)，表示能夠得到的最大金子數(shù)。

       輸入樣例：
       100 5
       77 92
       22 22
       29 87
       50 46
       99 90

       輸出樣例：
       133
      
       參考代碼如下：





/*
=========程序信息========
對(duì)應(yīng)題目：01背包之金礦模型
使用語(yǔ)言：c++
使用編譯器：Visual Studio 2005.NET
使用算法：動(dòng)態(tài)規(guī)劃
算法運(yùn)行時(shí)間：O(people * n) [people是人數(shù)，n是金礦數(shù)]
作者：貴州大學(xué)05級(jí) 劉永輝
昵稱：SDJL
編寫時(shí)間：2008年8月
聯(lián)系QQ：44561907
E-Mail：[email]44561907@qq.com[/email]
獲得更多文章請(qǐng)?jiān)L問我的博客：[url]www.cnblogs.com/sdjl[/url]
如果發(fā)現(xiàn)BUG或有寫得不好的地方請(qǐng)發(fā)郵件告訴我:)
轉(zhuǎn)載請(qǐng)保留此部分信息:)
*/

#include "stdafx.h"
#include <iostream>
#include <fstream>
using namespace std;

const int max_n = 100;//程序支持的最多金礦數(shù)
const int max_people = 10000;//程序支持的最多人數(shù)

int n;//金礦數(shù)
int peopleTotal;//可以用于挖金子的人數(shù)
int peopleNeed[max_n];//每座金礦需要的人數(shù)
int gold[max_n];//每座金礦能夠挖出來(lái)的金子數(shù)
int maxGold[max_people][max_n];//maxGold[j]保存了i個(gè)人挖前j個(gè)金礦能夠得到的最大金子數(shù)，等于-1時(shí)表示未知

//初始化數(shù)據(jù)
void init()
{
    ifstream inputFile("beibao.in");
    inputFile>>peopleTotal>>n;
    for(int i=0; i<n; i++)
        inputFile>>peopleNeed>>gold;
    inputFile.close();
            
    for(int i=0; i<=peopleTotal; i++)
        for(int j=0; j<n; j++)
            maxGold[j] = -1;//等于-1時(shí)表示未知 [對(duì)應(yīng)動(dòng)態(tài)規(guī)劃中的“做備忘錄”]
        
}

//獲得在僅有people個(gè)人和前mineNum個(gè)金礦時(shí)能夠得到的最大金子數(shù)，注意“前多少個(gè)”也是從0開始編號(hào)的
int GetMaxGold(int people, int mineNum)
{
    //申明返回的最大金子數(shù)
    int retMaxGold;

    //如果這個(gè)問題曾經(jīng)計(jì)算過  [對(duì)應(yīng)動(dòng)態(tài)規(guī)劃中的“做備忘錄”]
    if(maxGold[people][mineNum] != -1)
    {
        //獲得保存起來(lái)的值
        retMaxGold = maxGold[people][mineNum];
    }
    else if(mineNum == 0)//如果僅有一個(gè)金礦時(shí) [對(duì)應(yīng)動(dòng)態(tài)規(guī)劃中的“邊界”]
    {
        //當(dāng)給出的人數(shù)足夠開采這座金礦
        if(people >= peopleNeed[mineNum])
        {   
            //得到的最大值就是這座金礦的金子數(shù)
            retMaxGold = gold[mineNum];
        }
        else//否則這唯一的一座金礦也不能開采
        {
            //得到的最大值為0個(gè)金子
            retMaxGold = 0;
        }
    }
    else if(people >= peopleNeed[mineNum])//如果給出的人夠開采這座金礦 [對(duì)應(yīng)動(dòng)態(tài)規(guī)劃中的“最優(yōu)子結(jié)構(gòu)”]
    {
        //考慮開采與不開采兩種情況，取最大值
        retMaxGold = max(GetMaxGold(people - peopleNeed[mineNum],mineNum -1) + gold[mineNum],
                                        GetMaxGold(people,mineNum - 1));
    }
    else//否則給出的人不夠開采這座金礦 [對(duì)應(yīng)動(dòng)態(tài)規(guī)劃中的“最優(yōu)子結(jié)構(gòu)”]
    {
        //僅考慮不開采的情況
        retMaxGold  = GetMaxGold(people,mineNum - 1);
    }
   
    //做備忘錄   
    maxGold[people][mineNum] = retMaxGold;
    return retMaxGold;
}

int _tmain(int argc, _TCHAR* argv[])
{
    //初始化數(shù)據(jù)
    init();
    //輸出給定peopleTotal個(gè)人和n個(gè)金礦能夠獲得的最大金子數(shù)，再次提醒編號(hào)從0開始，所以最后一個(gè)金礦編號(hào)為n-1
    cout<<GetMaxGold(peopleTotal,n-1);
    system("pause");
    return 0;
}





歡迎光臨 (http://www.torrancerestoration.com/bbs/) Powered by Discuz! X3.1