JavaScript 动态规划&贪心算法

[Checkson]

前言

这一章，我们将介绍另外两种常用的算法：动态规划和贪心算法。动态规划常被人比作是递归的逆过程，而贪心算法在很多求优问题上，是不二之选。下面，我们针对这两种算法，展开详细的学习。

动态规划

动态规划有时为什么被认为是一种与递归相反的技术呢？是因为递归是从顶部开始将问题分解，通过解决掉所有分解出小问题的方式，来解决整个问题。动态规划解决方案从底部开始解决问题，将所有小问题解决掉，然后合并成一个整体解决方案，从而解决掉整个大问题。

使用递归去解决问题虽然简洁，但效率不高。包括 JavaScript 在内的众多语言，不能高效地将递归代码解释为机器代码，尽管写出来的程序简洁，但是执行效率低下。但这并不是说使用递归是件坏事，本质上说，只是那些指令式编程语言和面向对象的编程语言对递归 的实现不够完善，因为它们没有将递归作为高级编程的特性。

斐波拉契数列

斐波拉契数列定义为以下序列：

0，1，1，2，3，5，8，13，21，34，55，......

可以看到，当 n >= 2，a_n = a_{n - 1} + a_{n - 2}。这个数列的历史非常悠久，它是被公元700年一位意大利数学家斐波拉契用来描述在理想状态下兔子的增长情况。

不难看出，这个数列可以用一个简单的递归函数表示。

function fibo (n) {
    if (n <= 0)  return 0;
    if (n === 1) return 1;
    return fibo(n - 1) + fibo(n - 2);
}

这种实现方式非常耗性能，在n的数量级到达千级别，程序就变得特别慢，甚至失去响应。如果使用动态规划从它能解决的最简单子问题着手的话，效果就很不一样了。这里我们先用一个数组来存取每一次产生子问题的结果，方便后面求解使用。

function fibo (n) {
    if (n <= 0) return 0;
    if (n <= 1) return 1;
    var arr = [0, 1];
    for (var i = 2; i <= n; i++) {
        arr[i] = arr[i - 1] + arr[i - 2];
    }
    return arr[n];
}

细心的同学发现，这里的数组可以去掉，换做局部变量来实现可以省下不少内存空间。

function fibo (n) {
    if (n <= 0) return 0;
    if (n <= 1) return 1;
    var res, a = 0, b = 1;
    for (var i = 2; i <= n; i++) {
        res = a + b;
        a = b;
        b = res;
    }
    return res;
}

这里实现方式还有没有可能更简洁呢？答案是肯定的，我可以再节省一个变量。

function fibo (n) {
    if (n <= 0) return 0;
    if (n <= 1) return 1;
    var a = 0, b = 1;
    for (var i = 2; i <= n; i++) {
        b = a + b;
        a = b - a;
    }
    return b;
}

寻找最长公共子串

另一个适合使用动态规划去解决的问题是寻找两个字符串的最长公共子串。例如，在单词 raven 和 havoc中，最长的公共子串是“av”。寻找最长公共子串常用于遗传学中，用于使用核苷酸中碱基的首字母对DNA分子进行描述。

我们可以用暴力法去解决这个问题，但显得很笨拙。

function maxSubString (str1, str2) {
    if (!str1 || !str2) return '';
    var len1 = str1.length,
        len2 = str2.length;
    var maxSubStr = '';
    for (var i = 0; i < len1; i++) {
        for (var j = 0; j < len2; j++) {
            var tempStr = '',
                k = 0;
            while ((i + k < len1) && (j + k < len2) && (str1[i + k] === str2[j + k])) {
                tempStr += str1[i + k];
                k++;
            }
            if (tempStr.length >  maxSubStr.length) {
                maxSubStr = tempStr;
            }
        }
    }
    return maxSubStr;
}

求最长公共子串的动态规划算法，我们并不展开，有兴趣的同学可以跳转至以下链接：

• 求两个字符串的最长公共子串
• 动态规划：求最长公共子串/最长公共子序列

背包问题

背包问题是算法研究中的一个经典问题。试想你是一个保险箱大盗，打开了一个装满奇珍异宝的保险箱，但是你必须将这些宝贝放入你的一个小背包中。保险箱中的物品规格和价值不同。你希望自己的背包装进的宝贝总价值最大。

当然，暴力计算可以解决这个问题，但是动态规划会更为有效。使用动态规划来解决背包问题的关键思路是计算装入背包的每一个物品的最大价值，直到背包装满。

如果在我们例子中的保险箱中有 5 件物品，它们的尺寸分别是 3、4、7、8、9，而它们的价值分别是 4、5、10、11、13，且背包的容积为 16，那么恰当的解决方案是选取第三件物品和第五件物品，他们的总尺寸是 16，总价值是 23。

表1：0-1背包问题

物品	A	B	C	D	E
价值	4	5	10	11	13
尺寸	3	4	7	8	9

首先，我们看看递归方式怎么去解决这个问题：

function knapsack (capacity, objectArr, order) {
    if (order < 0 || capacity <= 0) {
        return 0;
    }
    if (arr[order].size > capacity) {
        return knapsack(capacity, objectArr, order - 1);
    }
    return Math.max(arr[order].value + knapsack(capacity - arr[order].size, objectArr, order - 1),
                    knapsack(capacity, objectArr, order - 1));
}

console.log(knapsack(16, [
    {value: 4, size: 3},
    {value: 5, size: 4},
    {value: 10, size: 7},
    {value: 11, size: 8},
    {value: 13, size: 9}
], 4)); // 23

为了提高程序的运行效率，我们不妨将递归实现方式改成动态规划。这个问题有个专业的术语：0-1背包问题。0-1背包问题，dp解法历来都困扰很多初学者，大多人学一次忘一次，那么，这次我们努力💪将它记在心里。

注意，理解0-1背包问题的突破口，就是要理解 “0-1” 这个含义，这里对于每一件物品，要么带走（1），要么留下（0)。

基本思路

0-1背包问题子结构：选择一个给定第 i 件物品，则需要比较选择第 i 件物品的形成的子问题的最优解与不选择第 i 件物品的子问题的最优解。分成两个子问题，进行选择比较，选择最优的。

若将 f[i][w] 表示前 i 件物品恰放入一个容量为 w 的背包可以获得的最大价值。则其状态转移方程便是：

f[i][w] = max{ f[i-1][w], f[i-1][w-w[i]]+v[i] }

其中，w[i] 表示第 i 件物品的重量，v[i] 表示第 i 件物品的价值。

function knapsack (capacity, objectArr) {
    var n = objectArr.length;
    var f = [];
    for (var i = 0; i <= n; i++) {
        f[i] = [];
        for (var w = 0; w <= capacity; w++) {
            if (i === 0 || w === 0) {
                f[i][w] = 0;
            } else if (objectArr[i - 1].size <= w) {
                var size = objectArr[i - 1].size,
                    value = objectArr[i - 1].value
                f[i][w] = Math.max(f[i - 1][w - size] + value, f[i - 1][w]);
            } else {
                f[i][w] = f[i - 1][w];
            }
        }
    }
    return f[n][capacity];
}

以上方法空间复杂度和时间复杂都是O(nm)，其中 n 为物品个数，m 为背包容量。时间复杂度没有优化的余地了，但是空间复杂我们可以优化到O(m)。首先我们要改写状态转移方程：

f[w] = max{ f[w], f[w-w[i]]+v[i] }

请看代码示例：

function knapsack (capacity, objectArr) {
    var n = objectArr.length;
    var f = [];
    for (var w = 0; w <= capacity; w++) {
        for (var i = 0; i < n; i++) {
            if (w === 0) {
                f[w] = 0;
            } else if (objectArr[i].size <= w) {
                var size = objectArr[i].size,
                    value = objectArr[i].value
                f[w] = Math.max(f[w - size] + value, f[w] || 0);
            } else {
                f[w] = Math.max(f[w] || 0, f[w - 1]);
            }
        }
    }
    return f[capacity];
}

贪心算法

前面研究的动态规划算法，它可以用于优化通过次优算法找到的解决方案——这些方案通常是基于递归方案实现的。对许多问题来说，采用动态规划的方式去处理有点大材小用，往往一个简单的算法就够了。

贪心算法就是一种比较简单的算法。贪心算法总是会选择当下的最优解，而不去考虑这一次的选择会不会对未来的选择造成影响。使用贪心算法通常表明，实现者希望做出的这一系列局部“最优”选择能够带来最终的整体“最优”选择。如果是这样的话，该算法将会产生一个最优解，否则，则会得到一个次优解。然而，对很多问题来说，寻找最优解很麻烦，这么做不值得，所以使用贪心算法就足够了。

背包问题

如果放入背包的物品从本质上说是连续的，那么就可以使用贪心算法来解决背包问题。换句话说，该物品必须是不能离散计数的，比如布匹和金粉。如果用到的物品是连续的，那么可以简单地通过物品的单价除以单位体积来确定物品的价值。在这种情况下的最优 是，先装价值最高的物品直到该物品装完或者将背包装满，接着装价值次高的物品，直到这种物品也装完或将背包装满，以此类推。我们把这种问题类型叫做 “部分背包问题”。

表2：部分背包问题

物品	A	B	C	D	E
价值	50	140	60	60	80
尺寸	5	20	10	12	20
比率	10	7	6	5	4

我们不能通过贪心算法来解决离散物品问题的原因，是因为我们无法将“半台电视”放入背包。换句话说，贪心算法不能解决0-1背包问题，因为在0-1背包问题下，你必须放入整个物品或者不放入。

function knapsack (capacity, objectArr) {
    // 首先按性价比排序, 高 -> 低
    objectArr.sort(function (a, b) {
        return parseFloat(b.value / b.size) - parseFloat(a.value / a.size);
    });
    // 记录物品个数
    var n = objectArr.length;
    // 记录已经选中尺寸，已选最大的最大价值
    var selected = 0,
        maxValue = 0;
    for (var i = 0; i < n && selected < capacity; i++) {
        var size = objectArr[i].size,
            value = objectArr[i].value;
        if (size <= capacity - selected) {
            maxValue += value;
            selected += size;
        } else {
            // 计算比例
            maxValue += value * ((capacity - selected) / size);
            selected  = capacity;
        }
    }
    return maxValue;
}

参考链接

• 0-1背包问题、贪心算法、动态规划
• 动态规划和贪心算法之背包问题理解