C#筆記：動態規劃演算法
- 2019 年 11 月 22 日
- 筆記
一個複雜的問題，通常逐級會分解成一系列小問題。而且很多情況下，某些小問題是相似的。但是使用傳統的遞歸，會將相同相似的小問題進行重複的計算。這樣浪費了算力。 所謂動態規劃演算法，實質是使用一個表，記錄下所有小問題的值。如果在計算中再次遇到相同問題，則直接取值。不做計算。顯然，如果每個小問題都是不同的，那麼此演算法沒有優勢。 比如斐波那契數列，就是一個簡單的例子。 定義：
Fab(n)= Fab(n-1)+Fab(n-2) Fab(1)=Fab(2)=1;
實現1：
static int GetFab(int n) { if (n == 1) return 1; if (n == 2) return 1; return GetFab(n - 1) + GetFab(n - 2); }
假如我們求Fab(5) 。那我們需要求Fab（4） +Fab（3）。 Fab(4)=Fab(3)+Fab(2)…..顯然。 Fab（3）被電腦不加區別的計算了兩次。而且隨著數字的增大，計算量是指數增長的。 如果我們使用一個數組，記錄下Fab的值。當Fab(n)!=null 時。直接讀取。那麼，我們就能把時間複雜度控制在 n 以內。 實現2：
static int[] fab = new int[6]; static int GetFabDynamic(int n) { if (n == 1) return fab[1] = 1; if (n == 2) return fab[2] = 1; if (fab[n] != 0)//如果存在，就直接返回。 { return fab[n]; } else //如果不存在，就進入遞歸，並且記錄下求得的值。 { return fab[n] = GetFabDynamic(n - 1) + GetFabDynamic(n - 2); } }
這就是，動態規劃演算法的 備忘錄模式。只需要把原來的遞歸稍微修改就行了。 下面是0-1背包問題的解法。可以對比一下。（一個限重w的背包，有許多件物品。sizes[n]保存他們的重量。values[n]保存它們的價值。求不超重的情況下背包能裝的最大價值）
static int[] size = new int[] { 3, 4, 7, 8, 9 };// 5件物品每件大小分別為3, 4, 7, 8, 9 且是不可分割的 0-1 背包問題 static int[] values = new int[] { 4, 5, 10, 11, 13 };//// 5件物品每件的價值分別為4, 5, 10, 11, 13 static int capacity = 16; static int[,] dp = new int[6, capacity + 1]; static int knapsack(int n, int w) { if (w < 0) return -10000; if (n == 0) return 0; if (dp[n, w] != 0) { return dp[n, w]; } else { return dp[n, w] = Math.Max(knapsack(n - 1, w), knapsack(n - 1, w - size[n - 1]) + values[n - 1]); /* * knapsack(n,w) 指在前N件物品在W剩餘容量下的最大價值。 * 這個公式的意思是，對於某一件物品， * 1、如果選擇裝進去，那麼，當前價值=前面的n-1件物品在空位w - size(n)下的最大價值（因為空位需要留出，空位也隱含了價值）。 * 再加上這件物品的價值。等於 knapsack(n - 1, w - size[n - 1]) + values[n - 1] * 2、 如果我們選擇不裝進去，那麼，在n-1物品的情況下空位仍然在，當前價值 = 前面n-1件物品在空位w下的最大價值。 * 等於knapsack(n - 1, w) * 注意：隨著演算，某一情況下的價值不會一成不變。 * 此時我們做出決策：到底是在裝入時的價值大，還是不裝入時的價值大呢？我們選擇上面兩種情況中值較大的。並記錄在案。 * 最後dp[N,M]就是我們要求的值。 */ } }
