<span role="heading" aria-level="2">js算法初窥05（算法模式02-动态规划与贪心算法）

大家好，又见面了，我是你们的朋友全栈君。

　　在前面的文章中（js算法初窥02（排序算法02-归并、快速以及堆排）我们学习了如何用分治法来实现归并排序，那么动态规划跟分治法有点类似，但是分治法是把问题分解成互相独立的子问题，最后组合它们的结果，而动态规划则是把问题分解成互相依赖的子问题。

　　那么我还有一个疑问，前面讲了递归，那么递归呢？分治法和动态规划像是一种手段或者方法，而递归则是具体的做操作的工具或执行者。无论是分治法还是动态规划或者其他什么有趣的方法，都可以使用递归这种工具来“执行”代码。

　　用动态规划来解决问题主要分为三个步骤：1、定义子问题，2、实现要反复执行来解决子问题的部分（比如用递归来“反复”），3、识别并求解出边界条件。这么说有点懵逼….那么我们试试用动态规划来解决一些经典的问题。

一、最少硬币找零问题

　　最少硬币找零问题是硬币找零问题的一个变种。硬币找零问题是给出要找零的钱数，以及可用的硬币面额以及对应的数量，找出有多少种找零的方法。最少硬币找零问题则是要找出其中所需最少数量的硬币。比如我们有1，5，10，25面额的硬币，如果要找36面额的钱，要如何找零呢？答案是一个25，一个10，一个1。这就是答案。那么如何把上面的问题转换成算法来解决呢？毕竟有了计算机很快速简单的就可以得到结果，不用我们再费力地用人脑去解决问题了，下面我们就来看一下代码：

//最少硬币找零
function MinCoinChange(coins) {
    // coins是有多少种面额的钱币。
    // 这里我们直接把构造函数传进来的参数用私有变量存储一下。
    var coins = coins;
    // 缓存结果集的变量对象
    var cache = {};
    // 定义一个构造函数的私有方法，
    this.makeChange = function (amount) {
        // 这里的this指向的就是this.makeChange私有函数本身，把它赋值给一个变量是为了不用在每次调用的时候都要计算（个人见解）
        var me = this;
        // amount就是我们要找零的钱数，如果为非正数，直接返回空数组，因为你找零的钱数不应该为负数。
        if(!amount) {
            return [];
        };
        
        // cache[amount]的判断是为了在重复计算前面已经计算过的结果时可以直接返回结果
        // 避免重复计算所造成的时间浪费
        if(cache[amount]) {
            return cache[amount];
        };
        // min用来存储最终结果的数组，newMin和newAmount分别是在逻辑的执行过程中，用于存储当前的符合条件的找零数组和找零钱数的。
        var min = [],newMin,newAmount;
        // 我们循环coins的长度。通过循环，我们为每一个conis数组中的面额都进行下面的逻辑操作。（主要是为当前coin做递归）
        for(var i = 0; i < coins.length; i++) {
            // 选择coins中的当前面额。
            var coin = coins[i];
            // 我们用要找零的钱数减去当前要找零的面额。并存储为newAmount变量。
            newAmount = amount - coin;
            // 在当前循环的递归中，如果newAmount是不小于0的值，也就是合法的找零的钱数，我们同样为该数调用找零方法。
            // 这里就是有点类似分而治之的那种策略了，递归求解。
            if(newAmount >= 0) {
                newMin = me.makeChange(newAmount);
            };
            // 在前面符合条件的newAmount递归后会进入下一个值得逻辑执行，然后就会到这里的逻辑判断
            // 下面的if判断主要是判断是否是当前的最优解，如果是，那么就放入我们最终的数组内。
            console.log(!min.length,min.length)
            if(newAmount >= 0 && (newMin.length < min.length - 1 || !min.length) && (newMin.length || !newAmount)) {
                min = [coin].concat(newMin);
                //console.log('new Min' + min + 'for' + amount);
            }
        };
        //cache存储了1到amount之间的所有结果
        //console.log(cache)
        return (cache[amount] = min);
    };
};

var minCoinChange = new MinCoinChange([1,5,10,25]);
console.log(minCoinChange.makeChange(36))

　　这是用动态规划的方法来解决最少硬币找零问题，那么我们再来看看如何用贪心算法求解最少硬币找零的问题。那么什么是贪心算法呢？贪心算法在有最优子结构的问题中尤为有效。最优子结构的意思是局部最优解能决定全局最优解。简单地说，问题能够分解成子问题来解决，子问题的最优解能递推到最终问题的最优解。贪心算法与动态规划的不同在于它对每个子问题的解决方案都做出选择，不能回退。动态规划则会保存以前的运算结果，并根据以前的结果对当前进行选择，有回退功能。

　　我们还是来看下代码：

function MinCoinChange(coins) {
    var coins = coins;
    this.makeChange = function (amount) {
        var change = [],total = 0;
        for(var i = coins.length; i >= 0; i--) {
            var coin = coins[i];
            while(total + coin <= amount) {
                change.push(coin);
                total += coin;
            }
        }
        return change;
    };
}

var minCoinChange = new MinCoinChange([1,5,10,25]);
console.log(minCoinChange.makeChange(36))

　　我们看上面的代码，主要逻辑跟动态规划十分相似，只是代码本身要简单了不少。贪心算法从我们的硬币中最大的开始拿，直到拿不了了再去拿下一个，直到返回最终结果。那么我们看看两种解决方法有什么不通过。动态规划会通过cache来缓存之前的计算结果，在当前的计算结果中与之前的对比，选择两者之间的最优解。而贪心算法则只是选择了当前的最优解，不会回退，也不会去存储记录之前的解决方案。

二、背包问题

　　背包问题其实是一个组合优化问题，问题是这样的，给定一个固定大小，能携带重量为W的背包，以及一组有价值和重量的物品，找出一个最佳解决方案，使得装入背包的物品总重量不超过W，且总价值是最大的。这个问题有两个版本，一个是0-1背包问题，该版本只允许背包里装入完整的物品，不能拆分。还有另外一个是可以装入分数物品。我们后面会用贪心算法来解决分数背包问题。

　　我们来看代码：

//背包问题
function knapSack(capacity,weights,values,n) {
    var i,w,a,b,kS = [];

    for (var i = 0; i <= n; i++) {
        kS[i] = [];
    }

    for(i = 0; i <= n; i++) {
        for(w = 0; w <= capacity; w++) {
            if(i == 0 || w == 0) {
                kS[i][w] = 0;
            } else if(weights[i - 1] <= w) {
                a = values[i - 1] + kS[i - 1][w - weights[i - 1]];
                b = kS[i - 1][w];
                kS[i][w] = (a > b) ? a : b;
            } else {
                kS[i][w] = kS[i - 1][w];
            }
        }
    }
    findValues(n,capacity,kS,weights,values);
    return kS[n][capacity];
};

function findValues(n,capacity,kS,weights,values) {
    var i = n,k = capacity;
    console.log('解决方案包括以下物品：');
    while(i > 0 && k > 0) {
        if(kS[i][k] !== kS[i - 1][k]) {
            console.log('物品' + i + ',重量：' + weights[i- 1] + ',价值：' + values[i - 1]);
            i--;
            k = k - kS[i][k];
        } else {
            i--;
        }
    }
}

var values = [3,4,5],weights = [2,3,4],capacity = 5,n = values.length;
console.log(knapSack(capacity,weights,values,n))

　　上面的代码中，我们最开始初始化一个矩阵，用来存放各种解决方案，而且要注意装入背包的物品i必须小于capacity，也就是小于背包可容纳的重量，才可以成为装入背包的一部分，不然你一个物品就超过了背包可容纳的重量，这是不允许的。并且当有两个物品重量相同的时候，我们选择价值较大的哪一个。

　　其实上面的算法还可以继续优化，这里不做多讲，大家有兴趣可以深入学习。

贪心算法的分数背包问题：

　　分数背包问题和0-1背包问题类似，只是我们可以在分数背包中加入部分的物品。代码并不难，大家自己写一下就明白了。

function knapSack(capacity,values,weights) {
    var n = values.length,load = 0,i = 0,val = 0;

    for(i = 0; i < n && load < capacity; i++) {
        if(weights[i] <= (capacity - load)) {
            val += values[i];
            load += weights[i];
        } else {
            var r = (capacity - load) / weights[i];
            val += r * values[i];
            load += weights[i];
        }
    }
    return val;
}
var values = [3,4,5],weights = [2,3,4],capacity = 6;

console.log(knapSack(capacity,values,weights))

三、最长公共子序列问题

　　该问题是这样的，找出两个字符串序列中的最长子序列的长度。最长子序列是指，在两个字符串序列中以相同的顺序出现，但不要求一定是连续的字符串序列。

//最长公共子序列LCS
function lcs(wordX,wordY) {
    var m = wordX.length,n = wordY.length,l = [],i,j,a,b;
    var solution = [];

    for (i = 0; i <= m; ++i) {
        l[i] = [];
        solution[i] = [];
        for(j = 0; j <= n; ++j) {
            l[i][j] = 0;
            solution[i][j] = '0';
        }
    }

    for(i = 0; i <= m; i++) {
        for(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 {
                a = l[i - 1][j];
                b = l[i][j - 1];
                l[i][j] = (a > b) ? a : b;
                solution[i][j] = (l[i][j] == l[i - 1][j]) ? 'top' : 'left';
            }
        }
    }
    printSolution(solution,l,wordX,wordY,m,n);
    return l[m][n];
}

function printSolution(solution,l,wordX,wordY,m,n) {
    var a = m,b = n,i,j,
    x = solution[a][b],
    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];
    }
    console.log('lcs:' + answer);
}

lcs("acbaed","abcadf");

四、矩阵链相乘

　　该问题是要找出一组矩阵相乘的最佳方式（顺序），在开始之前，有必要给大家简单讲解一下矩阵相乘，简单来说就是，加入一个n行m列的矩阵A和m行p列的矩阵B相乘，会得到一个n行p列的矩阵C。要注意，只有一个矩阵的行与另一个矩阵的列相同两个矩阵才可以想乘。

　　那么如果我想有A,B,C,D四个矩阵相乘，由于乘法满足结合律（小学数学知识点）。所以我们可以这样（A（B（CD））），或者这样（（AB）（CD））等五种相乘的方法，但是要注意的是，每种相乘的顺序不一样，我们的计算量也是不一样的。所以，我们来构建一个函数，找出计算量最少的相乘方法。这就是矩阵链相乘问题了。

//矩阵链相乘
function matrixChainOrder(p,n) {
    var i,j,k,l,q,m = [];


    //辅助矩阵s
    var s = [];
    for(i = 0; i <= n; i++) {
        s[i] = [];
        for(j = 0; j <= n; j++) {
            s[i][j] = 0;
        }
    }

    for(i = 0; i <= n; i++) {
        m[i] = [];
        m[i][i] = 0;
    };

    for(l = 2; l < n; l++) {
        for(i = 1; i <= n - l + 1; i++) {
            j = i + l - 1;
            m[i][j] = Number.MAX_SAFE_INTEGER;
            for(k = i; k <= j - 1; k++) {
                q = m[i][k] + m[k + 1][j] + p[i - 1]*p[k]*p[j];
                if(q < m[i][j]) {
                    m[i][j] = q;
                    s[i][j] = k;//辅助矩阵
                }
            }
        }
    }
    printOptimalParenthesis(s,1,n - 1);
    return m[1][n - 1];
}

function printOptimalParenthesis(s,i,j) {
    if(i == j) {
        console.log("A[" + i + "]");
    } else {
        console.log("(");
        printOptimalParenthesis(s,i,s[i][j]);
        printOptimalParenthesis(s,s[i][j] + 1,j);
        console.log(")");
    }
}

var p = [10,100,5,50,1,100];
n = p.length;
console.log(matrixChainOrder(p,n));