首頁  >  文章  >  後端開發  >  JS實作動態規劃背包演算法

JS實作動態規劃背包演算法

小云云
小云云原創
2018-03-22 15:28:232056瀏覽

面試時遇到一個背包演算法的題目,和傳統的背包稍有不同,是給定背包的容量和各種物品的重量,要求放入物品的總質量盡可能接近背包的容量並小於背包的容量,且放入的物品數目最少。本文主要和大家分享JS實現動態規劃背包演算法,希望能幫助大家。 function Backpack() {

            var totalWeight;//背包的总质量
            var goodsList = [];//可供选择的物品列表
            var bestMethodList = []//最优解的物品列表
            //设置背包总重量
            this.setTotalWeight = function(t) {
                totalWeight = t
            }
            //加物品
            this.addThing = function(goods) {
                goodsList.push(goods)
            }
            //减物品
            this.removeThing = function(goods) {
                var index = null
                goodsList.forEach(function(everyGoods,i){
                    if(everyGoods === goods){
                        index = i
                    }
                })
                if(index){
                    goodsList.splice(index,1)
                }
                else{
                    return false
                }
            }
            //计算最优解背包的重量
            this.count = function() {
                return getListWeight(bestMethodList)
            }
            //传入物品列表,返回该列表所有物品总质量
            function getListWeight(list) {
                var weight = 0
                list.forEach(function(everyGoods, i) {
                    weight += everyGoods.weight
                })
                return weight
            }
            //满足尽可能接近背包重量且放入物品最少的方法
            this.getBestMethod = function() {
                var arr = []
                //这里只需要两个参数 设置的重质量totalWeight和可供选择的物品goodsList
                goodsList.forEach(function(everyGoods, i) {
                    arr[i] = []//创建一个二维数组,放对应位置的最优解
                    for (let j = 0; j < totalWeight; j++) {
                        if(j+1 > everyGoods.weight) {
                            var newArr = [everyGoods]
                            if(i > 0){
                                var overWeight = j - everyGoods.weight
                                arr[i - 1][overWeight] ? newArr = newArr.concat(arr[i-1][overWeight]) : null
                                if(getListWeight(newArr) < getListWeight(arr[i-1][j])) {
                                    newArr = arr[i-1][j]
                                }
                                else if(getListWeight(newArr) === getListWeight(arr[i - 1][j]) && arr[i-1][j].length < newArr.length){
                                    newArr = arr[i-1][j]
                                }
                            }
                            arr[i][j] = newArr
                        }
                        else{
                            if(i === 0){
                                arr[i][j] = null
                            }
                            else{
                                arr[i][j] = arr[i-1][j]
                            }
                        }
                    }
                })
                return bestMethodList = arr[goodsList.length-1][totalWeight-1]
            }
        }
        //测试
        var myBag = new Backpack()
        myBag.setTotalWeight(10)
        myBag.addThing({name:&#39;apple&#39;,weight:1})
        myBag.addThing({ name: &#39;tomato&#39;, weight:3 })
        myBag.addThing({ name: &#39;ball&#39;, weight: 5 })
        myBag.addThing({ name: &#39;eggplant&#39;, weight: 4 })
        console.log(myBag.getBestMethod())//最优解的数组
        console.log(myBag.count())//最优解的质量

        其中的核心是創造一個二維數組保存局部的最優解,然後慢慢推演,最後獲得最終的最優解。

        演算法原則:

        (i對應行,j對應列,建立二維陣列arr)

     行物品的品質

        2.新的arr = arr【i-1】【背包剩餘品質】 + 目前物品(用concat)

#        3.新的arr 和上一行j列

        3.新的arr 和上一行j列的arr比較 (若初始條件不同,只需要改變這裡即可)

        4.依序得出arr

相關推薦:

JavaScript高階演算法之動態規劃實例分析

php演算法學習之動態規劃

#PHP動態規劃解決0-1背包問題實例分析_PHP教學

###

以上是JS實作動態規劃背包演算法的詳細內容。更多資訊請關注PHP中文網其他相關文章!

陳述:
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn