算法动态规划的代码优化详解(经典的背包问题)

CntChen 发布于2019-08-21 17:41 / 423人阅读

摘要：首先说下算法对于前端的作用和应用作用不用说了提高效率和性能应用目前也是买了算法导论这本书，看得头晕，各种数学知识需要返回去重新认识，哎，终于知道了以前学的东西总有用的。。。

首先说下算法对于前端的作用和应用

作用：不用说了提高效率和性能

应用：目前也是买了算法导论这本书，看得头晕，各种数学知识需要返回去重新认识，哎，终于知道了以前学的东西总有用的。。。，自己买的哭着也要读完，不扯了，直接说下现在已经应用的两个地方

1 trie树结构，对于后端扁平化数据转树形结构适用于前端的应用，终于把递归改成动规了

2 动态规划在前端瀑布流中的应用

第一点我也是看了这篇博客才下定决心迈向算法大坑的，具体不多说直接附上地址

http://www.cnblogs.com/ypinch...

第二点的动态规划参考以下博客，其中说的非常清晰，我主要是列举下对于此篇介绍中已实现的js，做空间复杂度优化的代码，不足之处请指出

https://segmentfault.com/a/11...

首先我是按照数据的倒退图里面以物品数组作为外层数组，背包容量作为内层数组的形式写的js（按照图的推导顺序）

1 用来生成随机大小的物品重量和价值数组

function getNum() {
        return parseInt(Math.random()*100+1);
    }
    function getArr(size) {
        var arr = [];
        for (var i = 0;i
2实现
function aaa(wight,value,all) {
            var startTime = new Date().getTime();
            var returnList = [];
            for (var i = 0;i=0?nowV:0;
                    fV = fV+(i>0&&returnList[i-1][lastW-1]?returnList[i-1][lastW-1]:0);
                    var nV = i>0&&returnList[i-1][j]?returnList[i-1][j]:0;
                    returnList[i][j] = Math.max(fV,nV);
                }
            }
            var endTime = new Date().getTime();
            return returnList[wight.length-1][all-1]+"耗时："+(endTime-startTime)+"ms";
        }
        console.log(aaa(weight,value,V));
}
这种方式需要构建庞大的二维缓存数组（用来把每次的最优解存下），这一步完全可以优化成只构建上一步的最优解供给下一次使用
function bbb(wight,value,all) {
            var startTime = new Date().getTime();
            var returnList = [];
            var returnList_prev = [];
            var flag = true;
            for (var i = 0;i=0?nowV:0;
                        fV = fV+(i>0&&returnList_prev[lastW-1]?returnList_prev[lastW-1]:0);
                        var nV = i>0&&returnList_prev[j]?returnList_prev[j]:0;
                        returnList[j] = Math.max(fV,nV);
                    } else {
                        var fV = lastW>=0?nowV:0;
                        fV = fV+(i>0&&returnList[lastW-1]?returnList[lastW-1]:0);
                        var nV = i>0&&returnList[j]?returnList[j]:0;
                        returnList_prev[j] = Math.max(fV,nV);
                    }
                    
                }
                flag = !flag;
            }
            var endTime = new Date().getTime();
            return returnList[all-1]+"耗时："+(endTime-startTime)+"ms";
        }
        console.log(bbb(weight,value,V));
}
对比了两次的结果时间分别是：

可以看到bbb方法明显比aaa快了一倍之多
这里只是想把自己看书后应用的东西分享下，大家有更好的方法也可以指正-。-

GPU云服务器云服务器学习算法的经典 java动态规划代码学习算法的经典书籍动态规划子序列代码

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/89862.html

算法动态规划的代码优化详解(经典的背包问题)

摘要：首先说下算法对于前端的作用和应用作用不用说了提高效率和性能应用目前也是买了算法导论这本书，看得头晕，各种数学知识需要返回去重新认识，哎，终于知道了以前学的东西总有用的。。。首先说下算法对于前端的作用和应用作用：不用说了提高效率和性能应用：目前也是买了算法导论这本书，看得头晕，各种数学知识需要返回去重新认识，哎，终于知道了以前学的东西总有用的。。。，自己买的哭着也要读完，不扯了，直...

oysun 2019-08-01 18:02 评论0 收藏0
算法动态规划的代码优化详解(经典的背包问题)

摘要：首先说下算法对于前端的作用和应用作用不用说了提高效率和性能应用目前也是买了算法导论这本书，看得头晕，各种数学知识需要返回去重新认识，哎，终于知道了以前学的东西总有用的。。。首先说下算法对于前端的作用和应用作用：不用说了提高效率和性能应用：目前也是买了算法导论这本书，看得头晕，各种数学知识需要返回去重新认识，哎，终于知道了以前学的东西总有用的。。。，自己买的哭着也要读完，不扯了，直...

galaxy_robot 2019-08-29 13:48 评论0 收藏0
经典动态规划--01背包问题

摘要：背包问题具体例子假设现有容量的背包，另外有个物品，分别为，，。最后，就是动态规划的思路了。而前个物体放入容量为的背包，又可以转化成前个物体放入背包的问题。背包问题具体例子：假设现有容量10kg的背包，另外有3个物品，分别为a1，a2，a3。物品a1重量为3kg，价值为4；物品a2重量为4kg，价值为5；物品a3重量为5kg，价值为6。将哪些物品放入背包可使得背包中的总价值最大？首先...

warkiz 2019-08-19 11:06 评论0 收藏0