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:'apple',weight:1}) myBag.addThing({ name: 'tomato', weight:3 }) myBag.addThing({ name: 'ball', weight: 5 }) myBag.addThing({ name: 'eggplant', weight: 4 }) console.log(myBag.getBestMethod())//最优解的数组 console.log(myBag.count())//最优解的质量
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
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!