算法動態規劃的代碼優化詳解(經典的背包問題)

oysun 發布于2019-08-01 18:02 / 478人閱讀

摘要：首先說下算法對于前端的作用和應用作用不用說了提高效率和性能應用目前也是買了算法導論這本書，看得頭暈，各種數學知識需要返回去重新認識，哎，終于知道了以前學的東西總有用的。。。

首先說下算法對于前端的作用和應用

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

應用：目前也是買了算法導論這本書，看得頭暈，各種數學知識需要返回去重新認識，哎，終于知道了以前學的東西總有用的。。。，自己買的哭著也要讀完，不扯了，直接說下現在已經應用的兩個地方

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動態規劃代碼學習算法的經典書籍動態規劃子序列代碼

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/51538.html

算法動態規劃的代碼優化詳解(經典的背包問題)

摘要：首先說下算法對于前端的作用和應用作用不用說了提高效率和性能應用目前也是買了算法導論這本書，看得頭暈，各種數學知識需要返回去重新認識，哎，終于知道了以前學的東西總有用的。。。首先說下算法對于前端的作用和應用作用：不用說了提高效率和性能應用：目前也是買了算法導論這本書，看得頭暈，各種數學知識需要返回去重新認識，哎，終于知道了以前學的東西總有用的。。。，自己買的哭著也要讀完，不扯了，直...

CntChen 2019-08-21 17:41 評論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