動態規劃-摘自百科

1.最優化原理（最優子結構性質） 最優化原理可這樣闡述：一個最優化策略具有這樣的性質，不論過去狀態和決策如何，對前面的決策所形成的狀態而言，余下的諸決策必須構成最優策略。簡而言之，一個最優化策略的子策略總是最優的。一個問題滿足最優化原理又稱其具有最優子結構性質。2.無后效性 將各階段按照一定的次序排列好之后，對于某個給定的階段狀態，它以前各階段的狀態無法直接影響它未來的決策，而只能通過當前的這個狀態。換句話說，每個狀態都是過去歷史的一個完整總結。這就是無后向性，又稱為無后效性。3.子問題的重疊性 動態規劃將原來具有指數級時間復雜度的搜索算法改進成了具有多項式時間復雜度的算法。其中的關鍵在于解決冗余，這是動態規劃算法的根本目的。動態規劃實質上是一種以空間換時間的技術，它在實現的過程中，不得不存儲產生過程中的各種狀態，所以它的空間復雜度要大于其它的算法。

例子01背包問題：

N件物品和一個容量為j的背包。第i件物品的體積是c[i]，價值是w[i]。求解將哪些物品裝入背包可使價值總和最大。基本思路這是最基礎的背包問題，特點是：每種物品僅有一件，可以選擇放或不放。用子問題定義狀態：即f[i][j]表示前i件物品恰放入一個容量為j的背包可以獲得的最大價值。則其狀態轉移方程便是：

01背包的狀態轉換方程（子問題的重疊性）

f[i,j] = Max{

f[i-1, j-c[i] ]+P[i]( j >= c[i] ), //選擇第i件物品，即前i-1件物品在體積為j-c[i]的背包的最大總價值+表示第i件物品的價值

f[i-1, j]//不選擇第i件物品

}

f[i,j]表示在前i件物品中選擇若干件放在體積為 j 的背包中，可以取得的最大價值。

P[i]表示第i件物品的價值。

現在的決策：為了背包中物品總價值最大化，第i件物品應該放入背包中嗎 ？（1放，0不放）

書包體積 10能裝的價值 對于a物品,選擇放進 =書包體積8能裝的價值(相對于bcde) + a物品價值 對于物品b選擇放進 =書包體積6能裝的價值(相對于cde)+ b物品價值 對于物品c選擇不放進 =書包體積6能裝的價值(相對于de) 對于物品d選擇不放進 =書包體積6能裝的價值(相對于e) == e物品價值所以: 書包體積 10能裝的價值 = a + b + e

例子分析來自：http://blog.csdn.net/mu399/article/details/7722810

附代碼：

 1 package test; 2  3 public class PackagePRoblem { 4     static int[][] rArr = new int[5][11];// 存儲最優解 ，rArr[i][0]不使用 5  6     public static void main(String[] args) { 7  8         String[] names = { "a", "b", "c", "d", "e" }; 9         int[] volumes = { 2, 2, 6, 5, 4 };10         int[] values = { 6, 3, 5, 4, 6 };11         int packageVolume = 10;12         int tail = 4;13 14         System.out.println("最優解得到的最大價值： "15                 + getBestValue(names, volumes, values, tail, packageVolume));16 17         for (int i = 0; i < rArr.length; i++) {18             for (int j = 0; j < rArr[i].length; j++) {19                 System.out.print(rArr[i][j]);20             }21             System.out.println();22         }23 24         getResult(packageVolume, names, volumes);25 26     }27 28     static void getResult(int reallyVolume, String[] names, int[] volumes) {29         System.out.println("最優解： ");30         int rowIndex = rArr.length - 1;31         while (reallyVolume > 0) {32             int nameIndex = 0, packageValue = 0;33             for (int i = 0; i <= rowIndex; i++) {//取出矩陣中第一次出現的最大值==對應的物品選擇放進背包34                 for (int j = 0; j <= reallyVolume; j++) {35                     if (rArr[i][j] > rArr[nameIndex][packageValue]) {36                         nameIndex = i;37                         packageValue = j;38                     }39                 }40             }41             System.out.println("nameIndex : " + nameIndex + " packageValue : "42                     + packageValue + " name: " + names[nameIndex]);43             if (nameIndex != 0) {44                 reallyVolume -= volumes[nameIndex];45             } else {46                 reallyVolume = 0;47             }48             rowIndex = nameIndex - 1;49         }50 51     }52 53     static int getBestValue(String[] names, int[] volumes, int[] values,54             int tail, int packageVolume) {55         if (tail == 0 && packageVolume >= volumes[0]) {56             return rArr[tail][packageVolume] = values[0];57         }58         int needTailValue = 0;59         int notNeedTailValue = 0;60 61         if (tail > 0) {62             int newPackageVolume = packageVolume - volumes[tail];63             if (newPackageVolume >= 0) {64                 if (rArr[tail][newPackageVolume] != 0) {// 減少重復計算65                     needTailValue = rArr[tail][newPackageVolume] + values[tail];66                 } else {67                     needTailValue = getBestValue(names, volumes, values,68                             tail - 1, newPackageVolume) + values[tail];69                 }70             }71 72             if (rArr[tail][packageVolume] != 0) {// 減少重復計算73                 notNeedTailValue = rArr[tail - 1][packageVolume];74             } else {75                 notNeedTailValue = getBestValue(names, volumes, values,76                         tail - 1, packageVolume);77             }78 79         }80 81         return rArr[tail][packageVolume] = Math.max(needTailValue,82                 notNeedTailValue);83     }84 85 }

result:最優解得到的最大價值： 150066666060600009990009000009900014000000900014000000000015最優解： nameIndex : 4 packageValue : 10 name: enameIndex : 1 packageValue : 4 name: bnameIndex : 0 packageValue : 2 name: a