JS implements dynamic programming knapsack algorithm-PHP Tutorial-php.cn

JS implements dynamic programming knapsack algorithm

小云云

Release： 2023-03-22 06:40:01

Original

2068 people have browsed it

During the interview, I encountered a question about the backpack algorithm. It is slightly different from the traditional backpack. Given the capacity of the backpack and the weight of various items, the total mass of the items placed is required to be as close as possible to the capacity of the backpack and smaller than the backpack. capacity and the minimum number of items placed. This article mainly shares with you the dynamic programming backpack algorithm implemented in JS. I hope it can help you. 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())//最优解的质量

Copy after login

The core is to create a two-dimensional array to save the local optimal solution, and then slowly deduce it, and finally obtain the final optimal solution.

using using using using out out through off ’s ’ through out out through out outmb together out right out out out out out out outmb out out out out out out out out out out out out , -- 1-. The quality of the items in the line

2. New arr = arr[i-1][Remaining mass of backpack] + current item (use concat)

3. New arr and column j of the previous row Comparison of arr (if the initial conditions are different, you only need to change here)

4. Obtain arr

Related recommendations:

JavaScript Advanced Algorithm Dynamic programming example analysis

php algorithm learning dynamic programming

PHP dynamic programming to solve the 0-1 knapsack problem example analysis_PHP tutorial

The above is the detailed content of JS implements dynamic programming knapsack algorithm. For more information, please follow other related articles on the PHP Chinese website!