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));

  最后,由于本人水平有限,能力与大神仍相差甚远,若有错误或不明之处,还望大家不吝赐教指正。非常感谢!

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏java一日一条

我是如何击败Java自带排序算法的

Java 8 对自带的排序算法进行了很好的优化。对于整形和其他的基本类型, Arrays.sort() 综合利用了双枢轴快速排序、归并排序和启发式插入排序。这个...

13010
来自专栏ml

错排公式

错排公式 百科名片 pala提出的问题: 十本不同的书放在书架上。现重新摆放,使每本书都不在原来放的位置。有几种摆法? 这个问题推广一下,就是错排问题: n个有...

41990
来自专栏后端技术探索

两道腾讯技术面试题(二面经历)

编程语言不限,主要考查两方面能力:1.算法逻辑能力。2.编码能力。笔者上次换工作,面试了十余家公司,其实很多关于算法逻辑的面试题都大同小异,每遇到一道题目就吃透...

11220
来自专栏落影的专栏

程序员进阶之算法练习(十五)

前言 有朋友推荐一个新的算法练习网站leetcode,说北美的公司招人都是400题起步,国内公司招聘也经常用到,上海的尤其多。 很有意思,可以花点时间做做le...

41850
来自专栏Python小屋

Python版组合数计算方法优化思路和源码

总体说明:本文的优化思路并不局限于Python,但C、C++、C#、Java等语言无法使用内置类型直接表示大整数,需要通过数组等特定形式并自己实现大整数乘除法才...

45350
来自专栏深度学习计算机视觉

算法基础+分治策略(算法复习第1弹)

马上就要算法考试了,好紧张,先复习第一波.... 参考文献(算法导论)+(张莉老师ppt) ---- 函数的增长,对算法效率的描述 渐进记号:Θ、Ω、O、o、...

33470
来自专栏Duncan's Blog

回溯法笔记

为了应用回溯法,所要求的解必须能表示成一个n-元组(x1,x2,…,xn),其中xi是取自某个有穷集Si。通常,所求解的问题需要求取一个使某一规范函数P(x1,...

11320
来自专栏一“技”之长

从一些简单的例子看算法时间复杂度 原

    在编程中,一段代码的执行效率实际上很难估算和预测,其主要受到如下几个方面的影响:

6410
来自专栏机器之心

入门 | 一文介绍机器学习中基本的数学符号

选自Machine Learning Mastery 作者:Jason Brownlee 机器之心编译 参与:Edison Ke、黄小天 本文介绍了机器学习中的...

37090
来自专栏算法channel

LeetCode实战:动态规划算法是怎么一回事

主要推送关于对算法的思考以及应用的消息。培养思维能力,注重过程,挖掘背后的原理,刨根问底。本着严谨和准确的态度,目标是撰写实用和启发性的文章,欢迎您的关注。 0...

33870

扫码关注云+社区

领取腾讯云代金券