乡下人产国偷v产偷v自拍,国产午夜片在线观看,婷婷成人亚洲综合国产麻豆,久久综合给合久久狠狠狠9

    • <output id="e9wm2"></output>
    <s id="e9wm2"><nobr id="e9wm2"><ins id="e9wm2"></ins></nobr></s> 
    

    • 
    
    
      



    
      
        
      
            
        
      
        
      
    
      
    
      
        
      
        
      
            
            
      
                
      
                    
                
      
                搜索
            
      

            分享
                
            

            
            
            
            
            
            
            
            

            
        
      
    
      
    
      

    
      

    
      
        
      
        
      
        
      
        
      
            
      
                
      
                    
      常用算法二（動態(tài)規(guī)劃）
      
                    
                    
                    
                    
      
                         第一閱覽室
                        
                        
                        2014-04-19
                        
                            
                        
                    
      
                    
      
                        
                        
      
                    
      
                    
                    
      
                        
      
                            
                        
      
                        
      
                            
                                
      
                                    
                                        
      

                                        
                                        

                                        
      一、基本概念
      

          動態(tài)規(guī)劃過程是：每次決策依賴于當(dāng)前狀態(tài)，又隨即引起狀態(tài)的轉(zhuǎn)移。一個(gè)決策序列就是在變化的狀態(tài)中產(chǎn)生出來的，所以，這種多階段最優(yōu)化決策解決問題的過程就稱為動態(tài)規(guī)劃。
      

      二、基本思想與策略
      

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

          由于動態(tài)規(guī)劃解決的問題多數(shù)有重疊子問題這個(gè)特點(diǎn)，為減少重復(fù)計(jì)算，對每一個(gè)子問題只解一次，將其不同階段的不同狀態(tài)保存在一個(gè)二維數(shù)組中。
      

          與分治法最大的差別是：適合于用動態(tài)規(guī)劃法求解的問題，經(jīng)分解后得到的子問題往往不是互相獨(dú)立的（即下一個(gè)子階段的求解是建立在上一個(gè)子階段的解的基礎(chǔ)上，進(jìn)行進(jìn)一步的求解）。
      

       
      

      

      三、適用的情況
      

      能采用動態(tài)規(guī)劃求解的問題的一般要具有3個(gè)性質(zhì)：
      

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

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

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

       
      

      

      四、求解的基本步驟
      

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

         初始狀態(tài)→│決策１│→│決策２│→…→│決策ｎ│→結(jié)束狀態(tài)
      

                            圖1 動態(tài)規(guī)劃決策過程示意圖
      

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

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

          (3)確定決策并寫出狀態(tài)轉(zhuǎn)移方程：因?yàn)闆Q策和狀態(tài)轉(zhuǎn)移有著天然的聯(lián)系，狀態(tài)轉(zhuǎn)移就是根據(jù)上一階段的狀態(tài)和決策來導(dǎo)出本階段的狀態(tài)。所以如果確定了決策，狀態(tài)轉(zhuǎn)移方程也就可寫出。但事實(shí)上常常是反過來做，根據(jù)相鄰兩個(gè)階段的狀態(tài)之間的關(guān)系來確定決策方法和狀態(tài)轉(zhuǎn)移方程。
      

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

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

      實(shí)際應(yīng)用中可以按以下幾個(gè)簡化的步驟進(jìn)行設(shè)計(jì)：
      

          （1）分析最優(yōu)解的性質(zhì)，并刻畫其結(jié)構(gòu)特征。
      

          （2）遞歸的定義最優(yōu)解。
      

          （3）以自底向上或自頂向下的記憶化方式（備忘錄法）計(jì)算出最優(yōu)值
      

          （4）根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造問題的最優(yōu)解
      

       
      

      

      五、算法實(shí)現(xiàn)的說明
      

          動態(tài)規(guī)劃的主要難點(diǎn)在于理論上的設(shè)計(jì)，也就是上面4個(gè)步驟的確定，一旦設(shè)計(jì)完成，實(shí)現(xiàn)部分就會非常簡單。
      

           使用動態(tài)規(guī)劃求解問題，最重要的就是確定動態(tài)規(guī)劃三要素：
      

          （1）問題的階段 （2）每個(gè)階段的狀態(tài)
      

          （3）從前一個(gè)階段轉(zhuǎn)化到后一個(gè)階段之間的遞推關(guān)系。
      

           遞推關(guān)系必須是從次小的問題開始到較大的問題之間的轉(zhuǎn)化，從這個(gè)角度來說，動態(tài)規(guī)劃往往可以用遞歸程序來實(shí)現(xiàn)，不過因?yàn)檫f推可以充分利用前面保存的子問題的解來減少重復(fù)計(jì)算，所以對于大規(guī)模問題來說，有遞歸不可比擬的優(yōu)勢，這也是動態(tài)規(guī)劃算法的核心之處。
      

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

      五、算法應(yīng)用示例
      

      

      用一個(gè)實(shí)際例子來體現(xiàn)動態(tài)規(guī)劃的算法思想——硬幣找零問題。
      

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

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

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

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

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

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

      算法描述：
      

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

      

      下面用代碼實(shí)現(xiàn)并測試一下： 
      

      1. public class CoinsChange {    
      2.     /**   
      3.      * 硬幣找零：動態(tài)規(guī)劃算法   
      4.      *    
      5.      * @param values   
      6.      *            :保存每一種硬幣的幣值的數(shù)組   
      7.      * @param valueKinds   
      8.      *            :幣值不同的硬幣種類數(shù)量，即coinValue[]數(shù)組的大小   
      9.      * @param money   
      10.      *            :需要找零的面值   
      11.      * @param coinsUsed   
      12.      *            :保存面值為i的紙幣找零所需的最小硬幣數(shù)   
      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.             // 當(dāng)用最小幣值的硬幣找零時(shí)，所需硬幣數(shù)量最多    
      22.             int minCoins = cents;    
      23.    
      24.             // 遍歷每一種面值的硬幣，看是否可作為找零的其中之一    
      25.             for (int kind = 0; kind < valueKinds; kind++) {                 
      26.                 // 若當(dāng)前面值的硬幣小于當(dāng)前的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.             // 保存最小硬幣數(shù)    
      35.             coinsUsed[cents] = minCoins;    
      36.    
      37.             System.out.println("面值為 " + (cents) + " 的最小硬幣數(shù) : "   
      38.                     + coinsUsed[cents]);    
      39.         }    
      40.     }    
      41.         
      42.     public static void main(String[] args) {    
      43.    
      44.         // 硬幣面值預(yù)先已經(jīng)按降序排列    
      45.         int[] coinValue = new int[] { 25, 21, 10, 5, 1 };    
      46.         // 需要找零的面值    
      47.         int money = 63;    
      48.         // 保存每一個(gè)面值找零所需的最小硬幣數(shù)，0號單元舍棄不用，所以要多加1    
      49.         int[] coinsUsed = new int[money + 1];    
      50.    
      51.         makeChange(coinValue, coinValue.length, money, coinsUsed);    
      52.     }    
      53. }   

      

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

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

      
背包建模：
      

      1. public class Knapsack {      
      2.         
      3.     /** 背包重量  */      
      4.     private int weight;      
      5.           
      6.     /** 背包物品價(jià)值  */      
      7.     private int value;      
      8.     /***   
      9.      * 構(gòu)造器   
      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 個(gè)背包，其重量分別為 w1,w2,……,wn, 價(jià)值分別為 v1,v2,……,vn   
      33.  * 要放入總承重為 totalWeight 的箱子中，    
      34.  * 求可放入箱子的背包價(jià)值總和的最大值。   
      35.  *    
      36.  * NOTE: 使用動態(tài)規(guī)劃法求解 背包問題   
      37.  * 設(shè) 前 n 個(gè)背包，總承重為 j 的最優(yōu)值為 v[n,j], 最優(yōu)解背包組成為 b[n];   
      38.  * 求解最優(yōu)值：   
      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.  * 求解最優(yōu)背包組成：   
      43.  * 1. 若 v[n,j] > v[n-1,j] 則 背包 n 被選擇放入 b[n],    
      44.  * 2. 接著求解前 n-1 個(gè)背包放入 j-wn 的總承重中，    
      45.  *    于是應(yīng)當(dāng)判斷 v[n-1, j-wn] VS v[n-2,j-wn], 決定 背包 n-1 是否被選擇。   
      46.  * 3. 依次逆推，直至總承重為零。   
      47.  *       
      48.  *    重點(diǎn)： 掌握使用動態(tài)規(guī)劃法求解問題的分析方法和實(shí)現(xiàn)思想。   
      49.  *    分析方法： 問題實(shí)例 P(n) 的最優(yōu)解S(n) 蘊(yùn)含 問題實(shí)例 P(n-1) 的最優(yōu)解S(n-1);   
      50.  *              在S(n-1)的基礎(chǔ)上構(gòu)造 S(n)    
      51.  *    實(shí)現(xiàn)思想： 自底向上的迭代求解 和 基于記憶功能的自頂向下遞歸   
      52.  */      
      53. public class KnapsackProblem {      
      54.           
      55.     /** 指定背包 */      
      56.     private Knapsack[] bags;      
      57.           
      58.     /** 總承重  */      
      59.     private int totalWeight;      
      60.           
      61.     /** 給定背包數(shù)量  */      
      62.     private int n;      
      63.           
      64.     /** 前 n 個(gè)背包，總承重為 totalWeight 的最優(yōu)值矩陣  */      
      65.     private int[][] bestValues;      
      66.           
      67.     /** 前 n 個(gè)背包，總承重為 totalWeight 的最優(yōu)值 */      
      68.     private int bestValue;      
      69.           
      70.     /** 前 n 個(gè)背包，總承重為 totalWeight 的最優(yōu)解的物品組成 */      
      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 個(gè)背包、給定總承重為 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.         // 求解最優(yōu)值      
      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 個(gè)背包重量大于總承重，則最優(yōu)解存在于前 i-1 個(gè)背包中，      
      104.                     // 注意：第 i 個(gè)背包是 bags[i-1]      
      105.                     if (j < bags[i-1].getWeight()) {      
      106.                         bestValues[i][j] = bestValues[i-1][j];      
      107.                     }         
      108.                     else       
      109.                     {      
      110.                         // 如果第 i 個(gè)背包不大于總承重，則最優(yōu)解要么是包含第 i 個(gè)背包的最優(yōu)解，      
      111.                         // 要么是不包含第 i 個(gè)背包的最優(yōu)解， 取兩者最大值，這里采用了分類討論法      
      112.                         // 第 i 個(gè)背包的重量 iweight 和價(jià)值 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 個(gè)背包      
      130.                tempWeight -= bags[i-1].getWeight();      
      131.            }      
      132.            if (tempWeight == 0) { break; }      
      133.         }      
      134.         bestValue = bestValues[n][totalWeight];      
      135.     }      
      136.           
      137.     /**   
      138.      * 獲得前  n 個(gè)背包， 總承重為 totalWeight 的背包問題的最優(yōu)解值   
      139.      * 調(diào)用條件： 必須先調(diào)用 solve 方法   
      140.      *    
      141.      */      
      142.     public int getBestValue() {       
      143.         return bestValue;      
      144.     }      
      145.           
      146.     /**   
      147.      * 獲得前  n 個(gè)背包， 總承重為 totalWeight 的背包問題的最優(yōu)解值矩陣   
      148.      * 調(diào)用條件： 必須先調(diào)用 solve 方法   
      149.      *    
      150.      */      
      151.     public int[][] getBestValues() {      
      152.               
      153.         return bestValues;      
      154.     }      
      155.           
      156.     /**   
      157.      * 獲得前  n 個(gè)背包， 總承重為 totalWeight 的背包問題的最優(yōu)解值矩陣   
      158.      * 調(diào)用條件： 必須先調(diào)用 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(" -------- 該背包問題實(shí)例的解: --------- ");      
      183.         System.out.println("最優(yōu)值：" + kp.getBestValue());       
      184.         System.out.println("最優(yōu)解【選取的背包】: ");      
      185.         System.out.println(kp.getBestSolution());      
      186.         System.out.println("最優(yōu)決策矩陣表：");      
      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. }      

      

      
                                          		
                                
      
                                  
                        
      
                    
      



                
      
                
      
                    
                    
                        
      
                            
                                
        
                                    		
                        
        
                            
                
        
                
        
                
                
                
        
                
        


                

                
        本站是提供個(gè)人知識管理的網(wǎng)絡(luò)存儲空間，所有內(nèi)容均由用戶發(fā)布，不代表本站觀點(diǎn)。請注意甄別內(nèi)容中的聯(lián)系方式、誘導(dǎo)購買等信息，謹(jǐn)防詐騙。如發(fā)現(xiàn)有害或侵權(quán)內(nèi)容，請點(diǎn)擊一鍵舉報(bào)。
        
                
                

                
        
                    轉(zhuǎn)藏
                    
                    
                    
                    
                    
                    
                        分享
                        
                        
                    
                    獻(xiàn)花（0）
                            
                
        
                
                
                
        
                    
        
                        
                        
                    
        
                
        

            
        

            
        

            
        
                
                
                
        
                
        
                    
        
                        
        0條評論
        
                        
                        
                        
        
                            
                            
        
                                發(fā)表
                            
        
                        
        
                        
                    
        
                    
                    
        請遵守用戶 評論公約
        
                    
                    
          
                    
        
                    
        
                    
        
                    
                
        
               
                
        
                    
        
                        類似文章
                        更多