JS implementiert einen Rucksackalgorithmus für die dynamische Programmierung

Während des Interviews bin ich auf eine Frage zum Rucksackalgorithmus gestoßen. Dieser unterscheidet sich geringfügig vom Fassungsvermögen des Rucksacks und dem Gewicht der verschiedenen Gegenstände auf das Fassungsvermögen des Rucksacks abgestimmt und kleiner als das Fassungsvermögen des Rucksacks und die Mindestanzahl der untergebrachten Gegenstände. In diesem Artikel wird hauptsächlich der in JS implementierte dynamische Programmierrucksackalgorithmus vorgestellt, in der Hoffnung, allen zu helfen. 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())//最优解的质量

Der Kern besteht darin, ein zweidimensionales Array zu erstellen, um die lokal optimale Lösung zu speichern, diese dann langsam abzuleiten und schließlich das endgültige Ergebnis zu erhalten optimale Lösung.

Algorithmusprinzip:

(i entspricht der Zeile, j entspricht der Spalte, erstellen Sie ein zweidimensionales Array arr)

1. Die verbleibende Masse des Rucksacks = die schwere Masse, die der aktuellen Spalte entspricht – die aktuelle Masse der Gegenstände in der Zeile

2. Neuer arr = arr [i-1] [verbleibende Masse des Rucksacks] + aktueller Gegenstand (mit concat)

3. Neuer arr und Spalte j der vorherigen Zeile Vergleich von arr (wenn die Anfangsbedingungen unterschiedlich sind, ändern Sie sie einfach hier)

4. Erhalten Sie arr

der Reihe nach Relevante Empfehlungen:

JavaScript Advanced Algorithm Dynamic Programming Beispielanalyse

Dynamic Programming for PHP Algorithm Learning

PHP Dynamische Programmierung zur Lösung des 0-1-Rucksackproblems – Beispielanalyse_PHP-Tutorial

Das obige ist der detaillierte Inhalt vonJS implementiert einen Rucksackalgorithmus für die dynamische Programmierung. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!