精品伊人久久大香线蕉,开心久久婷婷综合中文字幕,杏田冲梨,人妻无码aⅴ不卡中文字幕

打開APP
userphoto
未登錄

開通VIP，暢享免費電子書等14項超值服

開通VIP

首頁

好書

留言交流

下載APP

聯系客服
常用算法二（動態規劃）

一、基本概念

    動態規劃過程是：每次決策依賴于當前狀態，又隨即引起狀態的轉移。一個決策序列就是在變化的狀態中產生出來的，所以，這種多階段最優化決策解決問題的過程就稱為動態規劃。

二、基本思想與策略

    基本思想與分治法類似，也是將待求解的問題分解為若干個子問題（階段），按順序求解子階段，前一子問題的解，為后一子問題的求解提供了有用的信息。在求解任一子問題時，列出各種可能的局部解，通過決策保留那些有可能達到最優的局部解，丟棄其他局部解。依次解決各子問題，最后一個子問題就是初始問題的解。

    由于動態規劃解決的問題多數有重疊子問題這個特點，為減少重復計算，對每一個子問題只解一次，將其不同階段的不同狀態保存在一個二維數組中。

    與分治法最大的差別是：適合于用動態規劃法求解的問題，經分解后得到的子問題往往不是互相獨立的（即下一個子階段的求解是建立在上一個子階段的解的基礎上，進行進一步的求解）。

 

三、適用的情況

能采用動態規劃求解的問題的一般要具有3個性質：

    (1) 最優化原理：如果問題的最優解所包含的子問題的解也是最優的，就稱該問題具有最優子結構，即滿足最優化原理。

    (2) 無后效性：即某階段狀態一旦確定，就不受這個狀態以后決策的影響。也就是說，某狀態以后的過程不會影響以前的狀態，只與當前狀態有關。

   （3）有重疊子問題：即子問題之間是不獨立的，一個子問題在下一階段決策中可能被多次使用到。（該性質并不是動態規劃適用的必要條件，但是如果沒有這條性質，動態規劃算法同其他算法相比就不具備優勢）

 

四、求解的基本步驟

     動態規劃所處理的問題是一個多階段決策問題，一般由初始狀態開始，通過對中間階段決策的選擇，達到結束狀態。這些決策形成了一個決策序列，同時確定了完成整個過程的一條活動路線(通常是求最優的活動路線)。如圖所示。動態規劃的設計都有著一定的模式，一般要經歷以下幾個步驟。

   初始狀態→│決策１│→│決策２│→…→│決策ｎ│→結束狀態

                      圖1 動態規劃決策過程示意圖

    (1)劃分階段：按照問題的時間或空間特征，把問題分為若干個階段。在劃分階段時，注意劃分后的階段一定要是有序的或者是可排序的，否則問題就無法求解。

    (2)確定狀態和狀態變量：將問題發展到各個階段時所處于的各種客觀情況用不同的狀態表示出來。當然，狀態的選擇要滿足無后效性。

    (3)確定決策并寫出狀態轉移方程：因為決策和狀態轉移有著天然的聯系，狀態轉移就是根據上一階段的狀態和決策來導出本階段的狀態。所以如果確定了決策，狀態轉移方程也就可寫出。但事實上常常是反過來做，根據相鄰兩個階段的狀態之間的關系來確定決策方法和狀態轉移方程。

    (4)尋找邊界條件：給出的狀態轉移方程是一個遞推式，需要一個遞推的終止條件或邊界條件。

    一般，只要解決問題的階段、狀態和狀態轉移決策確定了，就可以寫出狀態轉移方程（包括邊界條件）。

實際應用中可以按以下幾個簡化的步驟進行設計：

    （1）分析最優解的性質，并刻畫其結構特征。

    （2）遞歸的定義最優解。

    （3）以自底向上或自頂向下的記憶化方式（備忘錄法）計算出最優值

    （4）根據計算最優值時得到的信息，構造問題的最優解

 

五、算法實現的說明

    動態規劃的主要難點在于理論上的設計，也就是上面4個步驟的確定，一旦設計完成，實現部分就會非常簡單。

     使用動態規劃求解問題，最重要的就是確定動態規劃三要素：

    （1）問題的階段 （2）每個階段的狀態

    （3）從前一個階段轉化到后一個階段之間的遞推關系。

     遞推關系必須是從次小的問題開始到較大的問題之間的轉化，從這個角度來說，動態規劃往往可以用遞歸程序來實現，不過因為遞推可以充分利用前面保存的子問題的解來減少重復計算，所以對于大規模問題來說，有遞歸不可比擬的優勢，這也是動態規劃算法的核心之處。

    確定了動態規劃的這三要素，整個求解過程就可以用一個最優決策表來描述，最優決策表是一個二維表，其中行表示決策的階段，列表示問題狀態，表格需要填寫的數據一般對應此問題的在某個階段某個狀態下的最優值（如最短路徑，最長公共子序列，最大價值等），填表的過程就是根據遞推關系，從1行1列開始，以行或者列優先的順序，依次填寫表格，最后根據整個表格的數據通過簡單的取舍或者運算求得問題的最優解。

五、算法應用示例

用一個實際例子來體現動態規劃的算法思想——硬幣找零問題。

硬幣找零問題描述：現存在一堆面值為 V1、V2、V3 … 個單位的硬幣，問最少需要多少個硬幣才能找出總值為 T 個單位的零錢？假設這一堆面值分別為 1、2、5、21、25 元，需要找出總值 T 為 63 元的零錢。

很明顯，只要拿出 3 個 21 元的硬幣就湊夠了 63 元了。

基于上述動態規劃的思想，我們可以從 1 元開始計算出最少需要幾個硬幣，然后再求 2 元、3元…每一次求得的結果都保存在一個數組中，以后需要用到時則直接取出即可。那么我們什么時候需要這些子問題的解呢？如何體現出由子問題的解得到較大問題的解呢？

其實，在我們從 1 元開始依次找零時，可以嘗試一下當前要找零的面值（這里指 1 元）是否能夠被分解成另一個已求解的面值的找零需要的硬幣個數再加上這一堆硬幣中的某個面值之和，如果這樣分解之后最終的硬幣數是最少的，那么問題就得到答案了。

單是上面的文字描述太抽象，先假定以下變量：

values[] : 保存每一種硬幣的幣值的數組
valueKinds :幣值不同的硬幣種類數量，即values[]數組的大小
money : 需要找零的面值
coinsUsed[] : 保存面值為 i 的紙幣找零所需的最小硬幣數

算法描述：

當求解總面值為 i 的找零最少硬幣數 coinsUsed[ i ] 時，將其分解成求解 coinsUsed[ i – cents]和一個面值為 cents 元的硬幣，由于 i – cents < i ， 其解 coinsUsed[ i – cents] 已經存在，如果面值為 cents 的硬幣滿足題意，那么最終解 coinsUsed[ i ] 則等于 coinsUsed[ i – cents] 再加上 1（即面值為 cents）的這一個硬幣。

下面用代碼實現并測試一下：

  1. public class CoinsChange {    
  2.     /**   
  3.      * 硬幣找零：動態規劃算法   
  4.      *    
  5.      * @param values   
  6.      *            :保存每一種硬幣的幣值的數組   
  7.      * @param valueKinds   
  8.      *            :幣值不同的硬幣種類數量，即coinValue[]數組的大小   
  9.      * @param money   
  10.      *            :需要找零的面值   
  11.      * @param coinsUsed   
  12.      *            :保存面值為i的紙幣找零所需的最小硬幣數   
  13.      */   
  14.     public static void makeChange(int[] values, int valueKinds, int money,    
  15.             int[] coinsUsed) {    
  16.    
  17.         coinsUsed[0] = 0;    
  18.         // 對每一分錢都找零，即保存子問題的解以備用，即填表    
  19.         for (int cents = 1; cents <= money; cents++) {    
  20.    
  21.             // 當用最小幣值的硬幣找零時，所需硬幣數量最多    
  22.             int minCoins = cents;    
  23.    
  24.             // 遍歷每一種面值的硬幣，看是否可作為找零的其中之一    
  25.             for (int kind = 0; kind < valueKinds; kind++) {                 
  26.                 // 若當前面值的硬幣小于當前的cents則分解問題并查表    
  27.                 if (values[kind] <= cents) {    
  28.                     int temp = coinsUsed[cents - values[kind]] + 1;    
  29.                     if (temp < minCoins) {    
  30.                         minCoins = temp;    
  31.                     }    
  32.                 }    
  33.             }    
  34.             // 保存最小硬幣數    
  35.             coinsUsed[cents] = minCoins;    
  36.    
  37.             System.out.println("面值為 " + (cents) + " 的最小硬幣數 : "   
  38.                     + coinsUsed[cents]);    
  39.         }    
  40.     }    
  41.         
  42.     public static void main(String[] args) {    
  43.    
  44.         // 硬幣面值預先已經按降序排列    
  45.         int[] coinValue = new int[] { 25, 21, 10, 5, 1 };    
  46.         // 需要找零的面值    
  47.         int money = 63;    
  48.         // 保存每一個面值找零所需的最小硬幣數，0號單元舍棄不用，所以要多加1    
  49.         int[] coinsUsed = new int[money + 1];    
  50.    
  51.         makeChange(coinValue, coinValue.length, money, coinsUsed);    
  52.     }    
  53. }   

0/1背包問題的動態規劃法求解，前人之述備矣，這里所做的工作，不過是自己根據理解實現了一遍，主要目的還是鍛煉思維和編程能力，同時，也是為了增進對動態規劃法機制的理解和掌握。 

      值得提及的一個問題是，在用 JAVA 實現時， 是按算法模型建模，還是用對象模型建模呢？ 如果用算法模型，那么 背包的值、重量就直接存入二個數組里；如果用對象模型，則要對背包以及背包問題進行對象建模。思來想去，還是采用了對象模型，盡管心里感覺算法模型似乎更好一些。有時確實就是這樣，對象模型雖然現在很主流，但也不是萬能的，采用其它的模型和視角，或許可以得到更好的解法。

背包建模：

  1. public class Knapsack {      
  2.         
  3.     /** 背包重量  */      
  4.     private int weight;      
  5.           
  6.     /** 背包物品價值  */      
  7.     private int value;      
  8.     /***   
  9.      * 構造器   
  10.      */      
  11.     public Knapsack(int weight, int value) {      
  12.         this.value = value;      
  13.         this.weight = weight;      
  14.     }      
  15.     public int getWeight() {      
  16.         return weight;      
  17.     }      
  18.           
  19.     public int getValue() {      
  20.         return value;      
  21.     }      
  22.           
  23.     public String toString() {      
  24.         return "[weight: " + weight + " " + "value: " + value + "]";        
  25.     }      
  26. }       
  27.   
  28. import java.util.ArrayList;      
  29.     
  30. /**   
  31.  * 求解背包問題：   
  32.  * 給定 n 個背包，其重量分別為 w1,w2,……,wn, 價值分別為 v1,v2,……,vn   
  33.  * 要放入總承重為 totalWeight 的箱子中，    
  34.  * 求可放入箱子的背包價值總和的最大值。   
  35.  *    
  36.  * NOTE: 使用動態規劃法求解 背包問題   
  37.  * 設 前 n 個背包，總承重為 j 的最優值為 v[n,j], 最優解背包組成為 b[n];   
  38.  * 求解最優值：   
  39.  * 1. 若 j < wn, 則 ： v[n,j] = v[n-1,j];   
  40.  * 2. 若  j >= wn, 則：v[n,j] = max{v[n-1,j], vn + v[n-1,j-wn]}。   
  41.  *    
  42.  * 求解最優背包組成：   
  43.  * 1. 若 v[n,j] > v[n-1,j] 則 背包 n 被選擇放入 b[n],    
  44.  * 2. 接著求解前 n-1 個背包放入 j-wn 的總承重中，    
  45.  *    于是應當判斷 v[n-1, j-wn] VS v[n-2,j-wn], 決定 背包 n-1 是否被選擇。   
  46.  * 3. 依次逆推，直至總承重為零。   
  47.  *       
  48.  *    重點： 掌握使用動態規劃法求解問題的分析方法和實現思想。   
  49.  *    分析方法： 問題實例 P(n) 的最優解S(n) 蘊含 問題實例 P(n-1) 的最優解S(n-1);   
  50.  *              在S(n-1)的基礎上構造 S(n)    
  51.  *    實現思想： 自底向上的迭代求解 和 基于記憶功能的自頂向下遞歸   
  52.  */      
  53. public class KnapsackProblem {      
  54.           
  55.     /** 指定背包 */      
  56.     private Knapsack[] bags;      
  57.           
  58.     /** 總承重  */      
  59.     private int totalWeight;      
  60.           
  61.     /** 給定背包數量  */      
  62.     private int n;      
  63.           
  64.     /** 前 n 個背包，總承重為 totalWeight 的最優值矩陣  */      
  65.     private int[][] bestValues;      
  66.           
  67.     /** 前 n 個背包，總承重為 totalWeight 的最優值 */      
  68.     private int bestValue;      
  69.           
  70.     /** 前 n 個背包，總承重為 totalWeight 的最優解的物品組成 */      
  71.     private ArrayList<Knapsack> bestSolution;      
  72.           
  73.     public KnapsackProblem(Knapsack[] bags, int totalWeight) {      
  74.         this.bags = bags;      
  75.         this.totalWeight = totalWeight;      
  76.         this.n = bags.length;      
  77.         if (bestValues == null) {      
  78.             bestValues = new int[n+1][totalWeight+1];      
  79.         }      
  80.     }      
  81.           
  82.     /**   
  83.      * 求解前 n 個背包、給定總承重為 totalWeight 下的背包問題   
  84.      *    
  85.      */      
  86.     public void solve() {      
  87.               
  88.         System.out.println("給定背包：");      
  89.         for(Knapsack b: bags) {      
  90.             System.out.println(b);      
  91.         }      
  92.         System.out.println("給定總承重: " + totalWeight);      
  93.               
  94.         // 求解最優值      
  95.         for (int j = 0; j <= totalWeight; j++) {      
  96.             for (int i = 0; i <= n; i++) {      
  97.                   
  98.                 if (i == 0 || j == 0) {      
  99.                     bestValues[i][j] = 0;      
  100.                 }         
  101.                 else       
  102.                 {      
  103.                     // 如果第 i 個背包重量大于總承重，則最優解存在于前 i-1 個背包中，      
  104.                     // 注意：第 i 個背包是 bags[i-1]      
  105.                     if (j < bags[i-1].getWeight()) {      
  106.                         bestValues[i][j] = bestValues[i-1][j];      
  107.                     }         
  108.                     else       
  109.                     {      
  110.                         // 如果第 i 個背包不大于總承重，則最優解要么是包含第 i 個背包的最優解，      
  111.                         // 要么是不包含第 i 個背包的最優解， 取兩者最大值，這里采用了分類討論法      
  112.                         // 第 i 個背包的重量 iweight 和價值 ivalue      
  113.                         int iweight = bags[i-1].getWeight();      
  114.                         int ivalue = bags[i-1].getValue();      
  115.                         bestValues[i][j] =       
  116.                             Math.max(bestValues[i-1][j], ivalue + bestValues[i-1][j-iweight]);            
  117.                     } // else      
  118.                 } //else               
  119.            } //for      
  120.         } //for      
  121.               
  122.         // 求解背包組成      
  123.         if (bestSolution == null) {      
  124.             bestSolution = new ArrayList<Knapsack>();      
  125.         }      
  126.         int tempWeight = totalWeight;      
  127.         for (int i=n; i >= 1; i--) {      
  128.            if (bestValues[i][tempWeight] > bestValues[i-1][tempWeight]) {      
  129.                bestSolution.add(bags[i-1]);  // bags[i-1] 表示第 i 個背包      
  130.                tempWeight -= bags[i-1].getWeight();      
  131.            }      
  132.            if (tempWeight == 0) { break; }      
  133.         }      
  134.         bestValue = bestValues[n][totalWeight];      
  135.     }      
  136.           
  137.     /**   
  138.      * 獲得前  n 個背包， 總承重為 totalWeight 的背包問題的最優解值   
  139.      * 調用條件： 必須先調用 solve 方法   
  140.      *    
  141.      */      
  142.     public int getBestValue() {       
  143.         return bestValue;      
  144.     }      
  145.           
  146.     /**   
  147.      * 獲得前  n 個背包， 總承重為 totalWeight 的背包問題的最優解值矩陣   
  148.      * 調用條件： 必須先調用 solve 方法   
  149.      *    
  150.      */      
  151.     public int[][] getBestValues() {      
  152.               
  153.         return bestValues;      
  154.     }      
  155.           
  156.     /**   
  157.      * 獲得前  n 個背包， 總承重為 totalWeight 的背包問題的最優解值矩陣   
  158.      * 調用條件： 必須先調用 solve 方法   
  159.      *    
  160.      */      
  161.     public ArrayList<Knapsack> getBestSolution() {      
  162.         return bestSolution;      
  163.     }      
  164.           
  165. }     
  166.   
  167. public class KnapsackTest {      
  168.         
  169.     public static void main(String[] args) {      
  170.               
  171.         Knapsack[] bags = new Knapsack[] {      
  172.                 new Knapsack(2,13), new Knapsack(1,10),      
  173.                 new Knapsack(3,24), new Knapsack(2,15),      
  174.                 new Knapsack(4,28), new Knapsack(5,33),      
  175.                 new Knapsack(3,20), new Knapsack(1, 8)      
  176.         };      
  177.             
  178.         int totalWeight = 10;      
  179.         KnapsackProblem kp = new KnapsackProblem(bags, totalWeight);      
  180.               
  181.         kp.solve();      
  182.         System.out.println(" -------- 該背包問題實例的解: --------- ");      
  183.         System.out.println("最優值：" + kp.getBestValue());       
  184.         System.out.println("最優解【選取的背包】: ");      
  185.         System.out.println(kp.getBestSolution());      
  186.         System.out.println("最優決策矩陣表：");      
  187.         int[][] bestValues = kp.getBestValues();      
  188.         for (int i=0; i < bestValues.length; i++) {      
  189.             for (int j=0; j < bestValues[i].length; j++) {      
  190.                 System.out.printf("%-5d", bestValues[i][j]);      
  191.             }      
  192.             System.out.println();      
  193.         }      
  194.     }      
  195. }      


本站僅提供存儲服務，所有內容均由用戶發布，如發現有害或侵權內容，請點擊舉報。
打開APP，閱讀全文并永久保存 查看更多類似文章
猜你喜歡
類似文章
理解貪心算法
運籌學的應用
貪心算法在背包背包問題中應用的探討
分治法，動態規劃，貪心算法比較
五大常用算法：分治、動態規劃、貪心、回溯、分支限界_搞怪的小丸子
動態規劃0/1背包問題
更多類似文章 >>
生活服務
分享 收藏 導長圖 關注 下載文章
綁定賬號成功
后續可登錄賬號暢享VIP特權！
如果VIP功能使用有故障，
可點擊這里聯系客服！

聯系客服

主站蜘蛛池模板： 屏山县| 安吉县| 海丰县| 富川| 固阳县| 邵武市| 邵东县| 隆化县| 开化县| 冕宁县| 乐都县| 沙雅县| 兖州市| 高州市| 新昌县| 长治县| 三亚市| 海安县| 公安县| 榆中县| 繁峙县| 光山县| 西畴县| 清苑县| 延津县| 石棉县| 九江县| 广饶县| 许昌市| 宜良县| 白银市| 滦南县| 临江市| 永丰县| 南平市| 通化县| 门头沟区| 太仓市| 海林市| 遂宁市| 天水市|