示例:背包問題的動態規劃解決方案
問題描述:
現在有壹種背包可以裝4磅重的物品。現在要把商場裏價值最高的物品拿出來裝進包裏。
商場裏的商品如下
每個動態規劃從壹個網格開始(如下所示)
現在逐行填充網格。
每個網格的計算公式:
填充吉他線當前最大值為1500(吉他)。
填充的揚聲器:當前最大值為3000(揚聲器)
填充筆記本:目前最大值3500(吉他+筆記本)
動態規劃的原理是將壹個大問題分解成許多小問題，先求出小問題的最優解，然後在考慮小問題最優解的前提下，得到最終問題的最優解。
在這個例子的背包問題中，我們首先在只有壹種吉他的情況下找到最優解，然後逐步添加物品，最後找到最優解。
網格計算公式的補充；
在求解動態規劃的整個過程中，從小問題層到大問題壹步步解決問題。自然，每個網格首先要考慮的點是前壹個網格的最大值，新的層又增加了新的物品，所以也要考慮新物品的值+剩余可用磅數的最大值(上層得到的)。
背包問題補充:
如果您添加另壹個項目-項鏈{ '價值':1000美元，'重量':0.5磅}
此時，如果使用先前的網格。
如果要打包的物品是燕麥、木豆、大米，可以壹部分壹部分拿出來。
動態編程解決不了這種情況，但是貪婪可以。
旅行路線問題
當然，我們可以用動態規劃的網格法來得到最有價值的旅遊路線。
如果加上以下景點，
在去巴黎景點的時間中，0.5天是從倫敦到巴黎的時間。
所以，如果先去埃菲爾鐵塔，去巴黎另外兩個景點的時間也會減少2個小時。
在這種情況下，不能使用前面的動態規劃算法。
動態算法處理的每個子問題都是離散的。
讓我們看看另壹個案例
如果要辦網站，網站的主要任務是:英語單詞翻譯。也就是用戶輸入英文單詞，妳給出相應的翻譯。比如用戶輸入魚，網站輸出魚。
如果用戶輸入hish，但是這個詞不在字典裏，此時應該給出壹個相似的詞。
類似的詞是什麽？確定子串的最大長度？
用動態規劃法求兩個字符串(fish和hish)的最大字符串長度
動態編程在解決問題之前總是需要知道網格中的元素:
兩個坐標軸是什麽？網格中的值是什麽(通常是要優化的指標)
1，分解問題:要求fish和hish的最大子串，可以先求它們串的最大公共子串(比如fis和his)。考慮到兩個坐標軸是兩個單詞，網格中的值就是最大子串的長度。
接下來，填寫網格。不斷驗證單元格公式:
單元格公式解釋:
1)都相同，則局部最大值字符串將被擴展，即對角線(單元格[i][j])上方的值將被加1(其中索引值在對角線方向累加)。
2)如果它們不同，則本地最大字符串為0。
兩個字符串的最大字符串長度是網格中的最大值3。
如果用戶進入fosh，是要返回fish還是fort？
如果根據最大子串判斷，會返回fort，但實際上fish和fosh更相似！
因此，我們考慮根據兩個字符串的最大公共* * *子序列長度(即兩個字符串的公共* * *字符數)進行判斷。
尋找最大公約數* * *子序列的單元格公式為:
fosh和fort的最長公共子序列是2。
fosh和fish的最長子序列為3。
此時，您可以返回正確的結果fish而不是fort。
1，動態規劃通常用於在給定的約束條件下優化壹個指標值。
2.動態規劃的原理是:把大問題分解成小問題，在解決小問題的條件下逐步解決大問題。分解問題的壹種方法是逐步減少條件，從最簡單的情況開始分析。
3.使用動態規劃的壹個必要條件是分解的每個小問題都是離散的。
4.每個動態規劃方案都設計有壹個網格。
4.1，每個格子都是小問題。
4.2、每個網格的值就是指標的值。
4.3、單元格計算公式需要具體問題具體分析。