面試時遇到一個背包演算法的題目,和傳統的背包稍有不同,是給定背包的容量和各種物品的重量,要求放入物品的總質量盡可能接近背包的容量並小於背包的容量,且放入的物品數目最少。本文主要和大家分享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:'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())//最优解的质量
其中的核心是創造一個二維數組保存局部的最優解,然後慢慢推演,最後獲得最終的最優解。
演算法原則:
(i對應行,j對應列,建立二維陣列arr)
行物品的品質
2.新的arr = arr【i-1】【背包剩餘品質】 + 目前物品(用concat)
# 3.新的arr 和上一行j列
3.新的arr 和上一行j列的arr比較 (若初始條件不同,只需要改變這裡即可) 4.依序得出arr相關推薦: ###以上是JS實作動態規劃背包演算法的詳細內容。更多資訊請關注PHP中文網其他相關文章!