function PackageItem (name, weight, value){
this.name = name;
this.weight = weight;
this.value = value;
}
function completeKnapsack(bagItems, bagsize) {
let length = bagItems.length;
var f = [];//f.length = bagsize + 1;
var answers = [];
for (var i = bagsize ; i >= 0; i--) {
f[i] = 0;
answers[i] = [];
}
for (var i = 0; i < length; i++) {
for (var weight = bagItems[i].weight; weight <= bagsize; weight++) {
if (f[weight] < f[weight - bagItems[i].weight] + bagItems[i].value) {
f[weight] = f[weight - bagItems[i].weight] + bagItems[i].value;
answers[weight] = answers[weight - bagItems[i].weight].slice() ;
answers[weight].push(bagItems[i].name);
}
}
}
answers[bagsize].forEach(function(item,index,array) {
console.log(item);
});
return f[bagsize];
}
let length = completeKnapsack(bagItems,11);
console.log(length);
完全背包
最后编辑于 :
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。
推荐阅读更多精彩内容
- 我在进行一些互联网公司的技术笔试的时候,对于我来说最大的难题莫过于最后的那几道编程题了,这对算法和数据结构有一定程...
- 很经典的动态规划问题,具体思路这里就不列出了,网上太多资料了。想要详细理解的话可以去看背包九讲这里分别列出,01背...
- 在阳朔期间突然兴起了学习精酿的念头,想学学精酿的历史,比利时精酿和德国精酿的区别,中国精酿的来龙去脉,在家自制手工...