面试时遇到一个背包算法的题目，和传统的背包稍有不同，是给定背包的容量和各种物品的重量，要求放入物品的总质量尽可能接近背包的容量并小于背包的容量，且放入的物品数目最少。本文主要和大家分享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）
1.背包剩余质量 = 当前列对应的重质量 - 当前行物品的质量
2.新的arr = arr【i-1】【背包剩余质量】 + 当前物品 （用concat）
3.新的arr 和 上一行j列的arr对比 （如果初始条件不同，只需要改这里即可）
4.依次得出arr
相关推荐：
