完全背包

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);

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容