動態規劃 動態規劃（Dynamic Programming，DP）是一種將複雜問題分解成更小的子問題來解決的優化演算法。下麵有一些用動態規劃來解決實際問題的演算法： 最少硬幣找零 給定一組硬幣的面額，以及要找零的錢數，計算出符合找零錢數的最少硬幣數量。例如，美國硬幣面額有1、5、10、25這四種面額，如 ...
動態規劃
動態規劃（Dynamic Programming，DP）是一種將複雜問題分解成更小的子問題來解決的優化演算法。下麵有一些用動態規劃來解決實際問題的演算法：
最少硬幣找零
給定一組硬幣的面額，以及要找零的錢數，計算出符合找零錢數的最少硬幣數量。例如，美國硬幣面額有1、5、10、25這四種面額，如果要找36美分的零錢，則得出的最少硬幣數應該是1個25美分、1個10美分和1個10美分共三個硬幣。這個演算法要解決的就是諸如此類的問題。我們來看看如何用動態規劃的方式來解決。
對於每一種面額，我們都分別計算所需要的硬幣數量。具體演算法如下：
- 如果全部用1美分的硬幣，一共需要36個硬幣
- 如果用5美分的硬幣，則需要7個5美分的硬幣 + 1個1美分的硬幣 = 8個硬幣
- 如果用10美分的硬幣，則需要3個10美分的硬幣 + 1個5美分的硬幣 + 1個1美分的硬幣 = 5個硬幣
- 如果用25美分的硬幣，則需要1個25美分的硬幣 + 1個10美分的硬幣 + 1個1美分的硬幣 = 3個硬幣
對應的示意圖如下：
方案4的硬幣總數最少，因此為最優方案。
具體的代碼實現如下：
function minCoinChange(coins, amount) { let result = null; if (!amount) return result; const makeChange = (index, value, min) => { let coin = coins[index]; let newAmount = Math.floor(value / coin); if (newAmount) min[coin] = newAmount; if (value % coin !== 0) { makeChange(--index, value - coin * newAmount, min); } }; const arr = []; for (let i = 0; i < coins.length; i++) { const cache = {}; makeChange(i, amount, cache); arr.push(cache); } console.log(arr); let newMin = 0; arr.forEach(item => { let min = 0; for (let v in item) min += item[v]; if (!newMin || min < newMin) { newMin = min; result = item; } }); return result; }
函數minCoinChange()接收一組硬幣的面額，以及要找零的錢數。我們將上面例子中的值傳入：
const result = minCoinChange2([1, 5, 10, 25], 36);
console.log(result);
得到如下結果：
[ { '1': 36 }, { '1': 1, '5': 7 }, { '1': 1, '5': 1, '10': 3 }, { '1': 1, '10': 1, '25': 1 } ] { '1': 1, '10': 1, '25': 1 }
上面的數組是我們在代碼中列印出來的arr的值，用來展示四種不同面額的硬幣作為找零硬幣時，實際所需要的硬幣種類和數量。最終，我們會計算arr數組中硬幣總數最少的那個方案，作為minCoinChange()函數的輸出。
當然在實際應用中，我們可以把硬幣抽象成任何你需要的數字，這個演算法能給出你滿足結果的最小組合。
背包問題
背包問題是一個組合優化問題，它被描述為：給定一個具有固定容量的背包capacity，以及一組具有價值（value）和重量（weight）的物品，找出一個最優方案，使得裝入背包的物品的總重量不超過capacity，且總價值最大。
假設我們有以下物品，且背包的總容量為5：
| 物品# | 重量 | 價值 |
| 1 | 2 | 3 |
| 2 | 3 | 4 |
| 3 | 4 | 5 |
我們用矩陣來解決這個問題。首先，我們把物品和背包的容量組成如下矩陣：
| 物品(i)/重量(w) | 0 | 1 | 2 | 3 | 4 | 5 |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 (w=2, v=3) | 0 | 0 |
a: 3+[0][2-2]=3+0 b: [0][2]=0 max(3+0,0)=3 |
a: 3+[0][3-2]=3+0 b: [0][3]=0 max(3+0,0)=3 |
a: 3+[0][4-3]=3+0 b: [0][4]=0 max(3+0,0)=3 |
a: 3+[0][5-3]=3+0 b: [0][5]=0 max(3+0,0)=3 |
| 2 (w=3, v=4) | 0 | 0 | 3 |
a: 4+[1][3-3]=4+0 b: [1][3]=3 max(4+0,3)=4 |
a: 4+[1][4-3]=4+0 b: [1][4]=3 max(4+0,3)=4 |
a: 4+[1][5-3]=4+3 b: [1][5]=3 max(4+3,3)=7 |
| 3 (w=4, v=5) | 0 | 0 | 3 | 4 |
a: 5+[2][4-4]=5+0 b: [2][4]=4 max(5+0,4)=5 |
a: 5+[2][5-4]=5+0 b: [2][5]=7 max(5+0,7)=7 |
為了便於理解，我們將矩陣kS的第一列和第一行忽略（因為它們表示的是容量0和第0個物品）。然後，按照要求往矩陣的格子里填數。如果當前的格子能放下對應的物品，存在以下兩種情況：
- a - 放入當前物品，然後剩餘的重量再放入前一個物品
- b - 不放入當前物品，放入前一個物品
在上面的表格中，
- 當背包的重量為1時，沒有物品能放入，所以都是0，這個很好理解。
- 當背包的重量為2時，物品1可以放入，那麼存在兩種情況：放入物品1（價值為3），剩餘的重量（背包的重量2減去物品1的重量2，結果為0）再放入前一個物品；不放入物品1，放入前一個物品[0][2]，價值為0。所以最大價值就是max(3, 0)=3。
- ......
- 當背包的重量為5時，放入物品2，兩種情況：放入物品2（價值為4），剩餘的重量（背包的重量5減去物品2的重量3，結果為2）再放入前一個物品，是[1][2]，對應的價值是3；不放入物品2，，放入前一個物品[1][5]，價值為3。所以最大價值就是max(4+3, 3)=7。
- ......
如果當前物品不能放入背包，則忽略它，用前一個值代替。我們可以按照上面描述的過程把剩餘的格子都填滿，這樣表格中最後一個單元格裡的值就是最優方案。
下麵是具體的實現代碼：
function knapSack(capacity, weights, values, n) { const kS = []; // 將ks初始化為一個空的矩陣 for (let i = 0; i <= n; i++) { kS[i] = []; } for (let i = 0; i <= n; i++) { for (let w = 0; w <= capacity; w++) { // 忽略矩陣的第1列和第1行 if (i === 0 || w === 0) { kS[i][w] = 0; } else if (weights[i - 1] <= w) { const a = values[i - 1] + kS[i - 1][w - weights[i - 1]]; const b = kS[i - 1][w]; kS[i][w] = Math.max(a, b); } else { kS[i][w] = kS[i - 1][w]; } } } console.log(kS); }
對於const a，其價值分為兩部分，第一部分就是它自己的價值（values[i - 1]），第二部分是用背包剩餘的重量（w - weights[i - 1]）裝進前一個物品（kS[i - 1]）。對於const b，就是找前一個能放入這個重量的物品（kS[i - 1][w]）。然後取這兩種情況下的最大值。
測試一下knapSack()函數，
const capacity = 5; const weights = [2, 3, 4]; const values = [3, 4, 5]; knapSack(capacity, weights, values, weights.length);
下麵是矩陣kS的輸出結果：
[ [ 0, 0, 0, 0, 0, 0 ], [ 0, 0, 3, 3, 3, 3 ], [ 0, 0, 3, 4, 4, 7 ], [ 0, 0, 3, 4, 5, 7 ] ]
最長公共子序列（LCS）
找出兩個字元串序列的最長子序列的長度。所謂最長子序列，是指兩個字元串序列中以相同順序出現，但不要求連續的字元串序列。例如下麵兩個字元串：
字元串1：acbaed
字元串2：abcadf
則LCS為acad。
和背包問題的思路類似，我們用下麵的表格來描述整個過程：
| a | b | c | a | d | f | ||
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | |
| a | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
| c | 0 | 1 | 1 | 2 | 2 | 2 | 2 |
| b | 0 | 1 | 2 | 2 | 2 | 2 | 2 |
| a | 0 | 1 | 2 | 2 | 3 | 3 | 3 |
| e | 0 | 1 | 2 | 2 | 3 | 3 | 3 |
| d | 0 | 1 | 2 | 2 | 3 | 4 | 4 |
矩陣的第一行和第一列都被設置為0，剩餘的部分，遵循下麵兩種情況：
- 如果wordX[i - 1]和wordY[j - 1]相等，則矩陣對應的單元格的值為單元格[i - 1][j - 1]的值加1。
- 如果wordX[i - 1]和wordY[j - 1]不相等，則找出單元格[i - 1][j]和單元格[i][j - 1]之間的最大值。
下麵是具體的實現代碼：
function lcs(wordX, wordY) { const m = wordX.length; const n = wordY.length; const l = []; for (let i = 0; i <= m; i++) { l[i] = []; for (let j = 0; j <= n; j++) { l[i][j] = 0; } } for (let i = 0; i <= m; i++) { for (let j = 0; j <= n; j++) { if (i === 0 || j === 0) { l[i][j] = 0; } else if (wordX[i - 1] === wordY[j - 1]) { l[i][j] = l[i - 1][j - 1] + 1; } else { const a = l[i - 1][j]; const b = l[i][j - 1]; l[i][j] = Math.max(a, b); } } } console.log(l); console.log(l[m][n]); }
我們將矩陣列印出來，結果如下：
const wordX = ['a', 'c', 'b', 'a', 'e', 'd']; const wordY = ['a', 'b', 'c', 'a', 'd', 'f']; lcs(wordX, wordY);
[ [ 0, 0, 0, 0, 0, 0, 0 ], [ 0, 1, 1, 1, 1, 1, 1 ], [ 0, 1, 1, 2, 2, 2, 2 ], [ 0, 1, 2, 2, 2, 2, 2 ], [ 0, 1, 2, 2, 3, 3, 3 ], [ 0, 1, 2, 2, 3, 3, 3 ], [ 0, 1, 2, 2, 3, 4, 4 ] ] 4
矩陣中最後一個單元格的值為LCS的長度。那如何計算出LCS的具體內容呢？我們可以設計一個相同的solution矩陣，用來做標記，如果wordX[i - 1]和wordY[j - 1]相等，則將solution矩陣中對應的值設置為'diagonal'，即上面表格中背景為灰色的單元格。否則，根據[i][j]和[i - 1][j]是否相等標記為'top'或'left'。然後通過printSolution()方法來找出LCS的內容。修改之後的代碼如下：
function printSolution(solution, wordX, m, n) { let a = m; let b = n; let x = solution[a][b]; let answer = ''; while (x !== '0') { if (solution[a][b] === 'diagonal') { answer = wordX[a - 1] + answer; a--; b--; } else if (solution[a][b] === 'left') { b--; } else if (solution[a][b] === 'top') { a--; } x = solution[a][b]; } return answer; } function lcs(wordX, wordY) { const m = wordX.length; const n = wordY.length; const l = []; const solution = []; for (let i = 0; i <= m; i++) { l[i] = []; solution[i] = []; for (let j = 0; j <= n; j++) { l[i][j] = 0; solution[i][j] = '0'; } } for (let i = 0; i <= m; i++) { for (let j = 0; j <= n; j++) { if (i === 0 || j === 0) { l[i][j] = 0; } else if (wordX[i - 1] === wordY[j - 1]) { l[i][j] = l[i - 1][j - 1] + 1; solution[i][j] = 'diagonal'; } else { const a = l[i - 1][j]; const b = l[i][j - 1]; l[i][j] = Math.max(a, b); solution[i][j] = l[i][j] === l[i - 1][j] ? 'top' : 'left'; } } } return printSolution(solution, wordX, m, n); }
測試結果：
const wordX = ['a', 'c', 'b', 'a', 'e', 'd']; const wordY = ['a', 'b', 'c', 'a', 'd', 'f']; console.log(lcs(wordX, wordY)); // acad
貪心演算法
貪心演算法遵循一種近似解決問題的技術，期盼通過每個階段的局部最優選擇，從而達到全局的最優。它不像動態規划算法那樣計算更大的格局。
最少硬幣找零
我們來看看如何用貪心演算法解決前面提到過的最少硬幣找零問題。
function minCoinChange(coins, amount) { const change = []; let total = 0; for (let i = coins.length - 1; i >= 0; i--) { const coin = coins[i]; while (total + coin <= amount) { change.push(coin); total += coin; } } return change; } const result = minCoinChange([1, 5, 10, 25], 36); console.log(result); // [ 25, 10, 1 ]
前提是coins數組已經按從小到大排好序了，貪心演算法從最大值開始嘗試，如果該值不滿足條件（要找零的錢數），則繼續向下找，直到找到滿足條件的所有值。以上演算法並不能滿足所有情況下找出最優方案，例如下麵這種情況：
const result = minCoinChange([1, 2, 5, 9, 10], 18); console.log(result); // [ 10, 5, 2, 1 ]
給出的結果[10, 5, 2, 1]並不是最優方案，最優方案應該是[9, 9]。
與動態規劃相比，貪心演算法更簡單、效率更高。但是其結果並不總是最理想的。但是綜合看來，它相對執行時間來說，輸出一個可以接受的結果。
背包問題
| 物品# | 重量 | 價值 |
| 1 | 2 | 3 |
| 2 | 3 | 4 |
| 3 | 4 | 5 |
在動態規劃的例子里，假定背包的容量為5，最佳方案是往背包里裝入物品1和物品2，總價值為7。在貪心演算法中，我們需要考慮分數的情況，假定背包的容量為6，裝入物品1和物品2之後，剩餘容量為1，可以裝入1/4的物品3，總價值為3+4+0.25×5=8.25。我們來看看具體的實現代碼：
function knapSack(capacity, weights, values) { const n = values.length; let load = 0; let val = 0; for (let i = 0; i < n && load < capacity; i++) { if (weights[i] <= capacity - load) { val += values[i]; load += weights[i]; console.log(`物品${i + 1}，重量：${weights[i]}，價值：${values[i]}`); } else { const r = (capacity - load) / weights[i]; val += r * values[i]; load += weights[i]; console.log(`物品${i + 1}的${r}，重量：${r * weights[i]}，價值：${val}`); } } return val; }
從第一個物品開始遍歷，如果總重量小於背包的容量，則繼續迭代，裝入物品。如果物品可以完整地裝入背包，則將其價值和重量分別計入到變數val和load中，同時列印裝入物品的信息。如果物品不能完整地裝入背包，計算能夠裝入的比例r，然後將這個比例所對應的價值和重量分別計入到變數val和load中，同時列印物品的信息。最終輸出總的價值val。下麵是測試結果：
const capacity = 6; const weights = [2, 3, 4]; const values = [3, 4, 5]; console.log(knapSack(capacity, weights, values));
物品1，重量：2，價值：3 物品2，重量：3，價值：4 物品3的0.25，重量：1，價值：8.25 8.25
在動態規划算法中，如果將背包的容量也設定為6，計算結果則為8。
最長公共子序列（LCS）
最後我們再來看看如何用貪心演算法解決LCS的問題。下麵的代碼返回了兩個給定數組中的LCS的長度：
function lcs(wordX, wordY, m = wordX.length, n = wordY.length) { if (m === 0 || n === 0) { return 0; } if (wordX[m - 1] === wordY[n - 1]) { return 1 + lcs(wordX, wordY, m - 1, n - 1); } const a = lcs(wordX, wordY, m, n - 1); const b = lcs(wordX, wordY, m - 1, n); return a > b ? a : b; } const wordX = ['a', 'c', 'b', 'a', 'e', 'd']; const wordY = ['a', 'b', 'c', 'a', 'd', 'f']; console.log(lcs(wordX, wordY)); // 4
