通過金礦模型介紹動態規劃
對於動態規劃，每個剛接觸的人都需要一段時間來理解，特別是第一次接觸的時候總是想不通為什麼這種方法可行，這篇文章就是為了幫助大家理解動態規劃，並通過講解基本的01揹包問題來引導讀者如何去思考動態規劃。本文力求通俗易懂，無異性，不讓讀者感到迷惑，引導讀者去思考，所以如果你在閱讀中發現有不通順的地方，讓你產生錯誤理解的地方，讓你難得讀懂的地方，請跟貼指出，謝謝！
----第一節----初識動態規劃--------
經典的01揹包問題是這樣的：
有乙個包和n個物品，包的容量為m，每個物品都有各自的體積和價值，問當從這n個物品中選擇多個物品放在包裡而物品體積總數不超過包的容量m時，能夠得到的最大價值是多少？[對於每個物品不可以取多次，最多只能取一次，之所以叫做01揹包，0表示不取，1表示取]
為了用一種生動又更形象的方式來講解此題，我把此題用另一種方式來描述，如下:
有乙個國家，所有的國民都非常老實憨厚，某天他們在自己的國家發現了十座金礦，並且這十座金礦在地圖上排成一條直線，國王知道這個訊息後非常高興，他希望能夠把這些金子都挖出來造福國民，首先他把這些金礦按照在地圖上的位置從西至東進行編號，依次為0、1、2、3、4、5、6、7、8、9，然後他命令他的手下去對每一座金礦進行勘測，以便知道挖取每一座金礦需要多少人力以及每座金礦能夠挖出多少金子，然後動員國民都來挖金子。
題目補充1：挖每一座金礦需要的人數是固定的，多乙個人少乙個人都不行。國王知道每個金礦各需要多少人手，金礦i需要的人數為peopleneeded[i]。
題目補充2：每一座金礦所挖出來的金子數是固定的，當第i座金礦有peopleneeded[i]人去挖的話，就一定能恰好挖出gold[i]個金子。否則乙個金子都挖不出來。
題目補充3：開採一座金礦的人完成開採工作後，他們不會再次去開採其它金礦，因此乙個人最多只能使用一次。
題目補充4：國王在全國範圍內僅招募到了10000名願意為了國家去挖金子的人，因此這些人可能不夠把所有的金子都挖出來，但是國王希望挖到的金子越多越好。
題目補充5：這個國家的每乙個人都很老實（包括國王），不會私吞任何金子，也不會弄虛作假，不會說謊話。
題目補充6：有很多人拿到這個題後的第一反應就是對每乙個金礦求出平均每個人能挖出多少金子，然後從高到低進行選擇，這裡要強調這種方法是錯的，如果你也是這樣想的，請考慮揹包模型，當有乙個揹包的容量為10，共有3個物品，體積分別是3、3、5，價值分別是6、6、9，那麼你的方法取到的是前兩個物品，總價值是12，但明顯最大值是後兩個物品組成的15。
題目補充7：我們只需要知道最多可以挖出多少金子即可，而不用關心哪些金礦挖哪些金礦不挖。
那麼，國王究竟如何知道在只有10000個人的情況下最多能挖出多少金子呢？國王是如何思考這個問題的呢？
國王首先來到了第9個金礦的所在地（注意，第9個就是最後乙個，因為是從0開始編號的，最西邊的那個金礦是第0個），他的臣子告訴他，如果要挖取第9個金礦的話就需要1500個人，並且第9個金礦可以挖出8888個金子。聽到這裡國王哈哈大笑起來，因為原先他以為要知道十個金礦在僅有10000個人的情況下最多能挖出多少金子是一件很難思考的問題，但是，就在剛才聽完他的臣子所說的那句話時，國王已經知道總共最多能挖出多少金子了，國王是如何在不了解其它金礦的情況下知道最多能挖出多少金子的呢？他的臣子們也不知道這個謎，因此他的臣子們就問他了：
「最聰明的國王陛下，我們都沒有告訴您其它金礦的情況，您是如何知道最終答案的呢？」
得意的國王笑了笑，然後把他最得意的「左、右手」叫到跟前，說到：「我並不需要考慮最終要挖哪些金礦才能得到最多的金子，我只需要考慮我面前的這座金礦就可以了，對於我面前的這座金礦不外乎僅有兩種選擇，要麼挖，要麼不挖，對吧？」
「當然，當然」大臣們回答倒。
國王繼續說道：「如果我挖取第9座金礦的話那麼我現在就能獲得8888個金子，而我將用去1500個人，那麼我還剩下8500個人。我親愛的左部下，，那麼我不就知道了在第9個金礦一定開採的情況下所能得到的最大金幣數嗎？
」國王的左部下聽後回答道：「國王陛下，您的意思是如果我能用8500個人在其它金礦最多開採出x個金幣的話，那您一共就能夠獲得x + 8888個金子，對嗎？」
「是啊，是啊……如果第9座金礦一定開採的話……」大臣們點頭說到。
國王笑著繼續對著他的右部下說到：「親愛的右部下，也許我並不打算開採這第9座金礦，那麼我依然擁有10000個人，如果我把這10000個人和剩下的金礦都給你的話，你最多能給我挖出多少個金子呢？」
國王的右部下聰明地說道：「尊敬的國王陛下，我明白您的意思了，如果我回答最多能購開採出y個金幣的話，那您就可以在y和x+8888之間選擇乙個較大者，而這個較大者就是最終我們能獲得的最大金幣數，您看我這樣理解對嗎？」
國王笑得更燦爛了，問他的左部下：「那麼親愛的左部下，我給你8500個人和其餘金礦的話你能告訴我最多能挖出多少金子嗎？
「請您放心，這個問題難不倒我」。左部下向國王打包票說到。
國王高興地繼續問他的右部下：「那右部下你呢，如果我給你10000個人和其餘金礦的話你能告訴我最多能挖出多少金子嗎？」
「當然能了！交給我吧！」右部下同左部下一樣自信地回答道。
「那就拜託給你們兩位了，現在我要回到我那舒適的王宮裡去享受了，我期待著你們的答覆。」國王說完就開始動身回去等訊息了，他是多麼地相信他的兩個大臣能夠給他乙個準確的答覆，因為國王其實知道他的兩位大臣要比他聰明得多。
故事發展到這裡，你是否在想國王的這兩個大臣又是如何找到讓國王滿意的答案的呢？他們為什麼能夠如此自信呢？事實上他們的確比國王要聰明一些，因為他們從國王的身上學到了一點，就是這一點讓他們充滿了自信。
國王走後，國王的左、右部下來到了第8座金礦，早已在那裡等待他們的金礦勘測兵向兩位大臣報道：「聰明的兩位大臣，您們好，第8座金礦需要1000個人才能開採，可以獲得7000個金子」。
因為國王僅給他的左部下8500個人，所以國王的左部下叫來了兩個人，對著其中乙個人問到：「如果我給你7500個人和除了第8、第9的其它所有金礦的話，你能告訴我你最多能挖出多少金子嗎？」
然後國王的左部下繼續問另乙個人：「如果我給你8500個人和除了第8、第9的其它所有金礦的話，你能告訴我你最多能挖出多少金子嗎？」
國王的左部下在心裡想著：「如果他們倆都能回答我的問題的話，那國王交給我的問題不就解決了嗎？哈哈哈！」
因為國王給了他的右部下10000個人，所以國王的右部下同樣也叫來了兩個人，對著其中乙個人問：「如果我給你9000個人和除了第8、第9的其它所有金礦的話，你能告訴我你最多能挖出多少金子嗎？」
然後國王的右部下繼續問他叫來的另乙個人：「如果我給你10000個人和除了第8、第9的其它所有金礦的話，你能告訴我你最多能挖出多少金子嗎？」
此時，國王的右部下同左部下一樣，他們都在為自己如此聰明而感到滿足。
當然，這四個被叫來的人同樣自信地回答沒有問題，因為他們同樣地從這兩個大臣身上學到了相同的一點，而兩位自認為自己一樣很聰明的大臣得意地笑著回到了他們的府邸，等著別人回答他們提出來的問題，現在你知道了這兩個大臣是如何解決國王交待給他們的問題了嗎？
那麼你認為被大臣叫去的那四個人又是怎麼完成大臣交給他們的問題的呢？答案當然是他們找到了另外八個人！
沒用多少功夫，這個問題已經在全國傳開了，更多人的人找到了更更多的人來解決這個問題，而有些人卻不需要去另外找兩個人幫他，哪些人不需要別人的幫助就可以回答他們的問題呢？
很明顯，當被問到給你z個人和僅有第0座金礦時最多能挖出多少金子時，就不需要別人的幫助，因為你知道，如果z大於等於挖取第0座金礦所需要的人數的話，那麼挖出來的最多金子數就是第0座金礦能夠挖出來的金子數，如果這z個人不夠開採第0座金礦，那麼能挖出來的最多金子數就是0，因為這唯一的金礦不夠人力去開採。讓我們為這些不需要別人的幫助就可以準確地得出答案的人們鼓掌吧，這就是傳說中的底層勞動人民！
故事講到這裡先暫停一下，我們現在重新來分析一下這個故事，讓我們對動態規劃有個理性認識。
子問題：
國王需要根據兩個大臣的答案以及第9座金礦的資訊才能判斷出最多能夠開採出多少金子。為了解決自己面臨的問題，他需要給別人製造另外兩個問題，這兩個問題就是子問題。
思考動態規劃的第一點----最優子結構：
國王相信，只要他的兩個大臣能夠回答出正確的答案（對於考慮能夠開採出的金子數，最多的也就是最優的同時也就是正確的），再加上他的聰明的判斷就一定能得到最終的正確答案。我們把這種子問題最優時母問題通過優化選擇後一定最優的情況叫做「最優子結構」。
思考動態規劃的第二點----子問題重疊：
實際上國王也好，大臣也好，所有人面對的都是同樣的問題，即給你一定數量的人，給你一定數量的金礦，讓你求出能夠開採出來的最多金子數。我們把這種母問題與子問題本質上是同乙個問題的情況稱為「子問題重疊」。然而問題中出現的不同點往往就是被子問題之間傳遞的引數，比如這裡的人數和金礦數。
思考動態規劃的第三點----邊界：
想想如果不存在前面我們提到的那些底層勞動者的話這個問題能解決嗎？永遠都不可能！我們把這種子問題在一定時候就不再需要提出子子問題的情況叫做邊界，沒有邊界就會出現死迴圈。
動態規劃入門
分類 演算法與資料結構 2.6其他問題 還有一些題目雖和一寫基本模型相似但又有區別，我也就不總結共性了，列出它們，看看他們的狀態又是怎麼設計的 例題25 花店櫥窗設計 flower.pas c cpp ioi或巴蜀評測系統 問題描述 假設以最美觀的方式布置花店的櫥窗，有f束花，每束花的品種都不一樣，...
動態規劃入門
分類 演算法與資料結構 2.5石子合併問題 也有人把這類問題叫做是區間上的動態規劃。例題22 石子合併 stone.pas c cpp 某年noi 去巴蜀交 問題描述 在乙個操場上擺放著一行共n堆的石子。現要將石子有序地合併成一堆。規定每次只能選相鄰的兩堆合併成新的一堆，並將新的一堆石子數記為該次合...
理財規劃入門作業
一 單項選擇題 請從四個備選答案中選擇1個正確的答案，用字母填寫到括號內 l 在理財規劃過程中，屬於客戶職責的是 2005.12專1 a a 提出需求b 編制家庭資產負債表 c 確定理財目標d 經濟環境分析 2 在與客戶的交流溝通中，一般不建議理財規劃師採用 方式進行提問。2005.12專6 a 誘...