首页 / JAVASCRIPT / JS实现动态规划背包算法
JS实现动态规划背包算法
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了JS实现动态规划背包算法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2634字，纯文字阅读大概需要4分钟。
内容图文
面试时遇到一个背包算法的题目，和传统的背包稍有不同，是给定背包的容量和各种物品的重量，要求放入物品的总质量尽可能接近背包的容量并小于背包的容量，且放入的物品数目最少。本文主要和大家分享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
相关推荐：
JavaScript高级算法之动态规划实例分析
php算法学习之动态规划
PHP动态规划解决0-1背包问题实例分析_PHP教程
以上就是JS实现动态规划背包算法的详细内容，更多请关注Gxl网其它相关文章！
内容总结
以上是互联网集市为您收集整理的JS实现动态规划背包算法全部内容，希望文章能够帮你解决JS实现动态规划背包算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。