JS implémente un algorithme de programmation dynamique

小云云
Libérer: 2023-03-22 06:40:01
original
2049 Les gens l'ont consulté

J'ai rencontré une question sur l'algorithme du sac à dos lors de l'entretien. Il est légèrement différent du sac à dos traditionnel. Compte tenu de la capacité du sac à dos et du poids des différents objets, la masse totale des objets placés doit être la plus proche possible. à la capacité du sac à dos et inférieure à la capacité du sac à dos et au nombre minimum d'articles placés. Cet article partage principalement avec vous l'algorithme du sac à dos de programmation dynamique implémenté dans JS. J'espère qu'il pourra vous aider. 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())//最优解的质量
Copier après la connexion

L'essentiel est de créer un tableau bidimensionnel pour enregistrer la solution optimale locale, puis de la déduire lentement, et enfin d'obtenir la solution finale solution optimale.

Principe de l'algorithme :

(i correspond à la ligne, j correspond à la colonne, créer un tableau bidimensionnel arr)

1. La masse restante du sac à dos = la masse lourde correspondant à la colonne actuelle - l'actuelle La masse des objets dans la ligne

2. New arr = arr [i-1] [masse restante du sac à dos] + objet courant (en utilisant concat)

3. Nouveau arr et colonne j de la ligne précédente Comparaison des arr (si les conditions initiales sont différentes, il suffit de changer ici)

4. Obtenir arr

en séquence Recommandations pertinentes :

Analyse d'exemples de programmation dynamique d'algorithme avancé JavaScript

Programmation dynamique pour l'apprentissage d'algorithmes PHP

PHP Programmation dynamique pour résoudre l'exemple de problème de sac à dos 0-1 Analysis_PHP Tutorial

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!

Étiquettes associées:
source:php.cn
Déclaration de ce site Web
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn
Tutoriels populaires
Plus>
Derniers téléchargements
Plus>
effets Web
Code source du site Web
Matériel du site Web
Modèle frontal
À propos de nous Clause de non-responsabilité Sitemap
Site Web PHP chinois:Formation PHP en ligne sur le bien-être public,Aidez les apprenants PHP à grandir rapidement!