动态规划

　　动态规划（Dynamic Programming，DP）是一种将复杂问题分解成更小的子问题来解决的优化算法。下面有一些用动态规划来解决实际问题的算法：

最少硬币找零

　　给定一组硬币的面额，以及要找零的钱数，计算出符合找零钱数的最少硬币数量。例如，美国硬币面额有1、5、10、25这四种面额，如果要找36美分的零钱，则得出的最少硬币数应该是1个25美分、1个10美分和1个10美分共三个硬币。这个算法要解决的就是诸如此类的问题。我们来看看如何用动态规划的方式来解决。

　　对于每一种面额，我们都分别计算所需要的硬币数量。具体算法如下：

1. 如果全部用1美分的硬币，一共需要36个硬币
2. 如果用5美分的硬币，则需要7个5美分的硬币 + 1个1美分的硬币 = 8个硬币
3. 如果用10美分的硬币，则需要3个10美分的硬币 + 1个5美分的硬币 + 1个1美分的硬币 = 5个硬币
4. 如果用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. 当背包的重量为1时，没有物品能放入，所以都是0，这个很好理解。
2. 当背包的重量为2时，物品1可以放入，那么存在两种情况：放入物品1（价值为3），剩余的重量（背包的重量2减去物品1的重量2，结果为0）再放入前一个物品；不放入物品1，放入前一个物品[0][2]，价值为0。所以最大价值就是max(3, 0)=3。
3. ......
4. 当背包的重量为5时，放入物品2，两种情况：放入物品2（价值为4），剩余的重量（背包的重量5减去物品2的重量3，结果为2）再放入前一个物品，是[1][2]，对应的价值是3；不放入物品2，，放入前一个物品[1][5]，价值为3。所以最大价值就是max(4+3, 3)=7。
5. ......

　　如果当前物品不能放入背包，则忽略它，用前一个值代替。我们可以按照上面描述的过程把剩余的格子都填满，这样表格中最后一个单元格里的值就是最优方案。

　　下面是具体的实现代码：

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