01 01背包

function PackageItem (name, weight, value){
    this.name = name;
    this.weight = weight;
    this.value = value;
}

function get01PackageAnswer(bagItems , bagsize) {
    var bagMatrix = [];
    var i ;
    var item;

    for (i = 0; i < bagItems.length; i++) {
        bagMatrix[i] = [0];
    }

    for (i = 1; i <= bagsize;i++) {
        for (var j = 0; j < bagItems.length; j++) {
            item = bagItems[j];
            if (item.weight > i) 
            {
                if (j==0) {
                    bagMatrix[j][i] = 0;
                } else {
                    bagMatrix[j][i] = bagMatrix[j-1][i];
                }
            }
            else 
            {
                var itemInBag;
                if (j == 0) {
                    bagMatrix[j][i] = item.value;
                    continue ;
                } else {
                    itemInBag = bagMatrix[j-1][i-item.weight] + item.value; //向上向下找都无所谓，只要安一定的顺序找就行了
                }
                bagMatrix[j][i] = (bagMatrix[j-1][i] > itemInBag ? bagMatrix[j-1][i] : itemInBag);//比较下现在的情况是不是比不动要好 0+6 < 7 就不动 因为他是拿下面一组的值进行比较，所以永远不会可能出现已经选过的情况。
            }
        }
    }

    var answers = [];
    var curSize = bagsize;

    for ( i = bagItems.length - 1; i >= 0; i--) {
        item = bagItems[i];
        if (curSize == 0) 
            break;
        
        if (i == 0 && curSize  > 0) {
            answers.push(item.name);
            break;
        }

        if (bagMatrix[i][curSize] - bagMatrix[i-1][curSize - item.weight] == item.value) {
            answers.push(item.name);
            curSize -= item.weight;
        }
    }
    return answers;
}

var nameArr = ['a','b','c','d','e'];
var weightArr = [2,2,6,5,4];
var valueArr = [6,3,5,4,6];


var bagItems = [];

for (var i = 0; i < nameArr.length; i++) {
    var bagItem = new PackageItem(nameArr[i],weightArr[i],valueArr[i]);
    bagItems[i] = bagItem;
}

var arr = get01PackageAnswer(bagItems,10);

arr.forEach(function(item,index,array) {
    console.log(item);
})