Knapsack algorithm in JavaScript

knapsack.js

//Knapsack algorithm
//==================
// wikipedia: [Knapsack (0/1)](http://en.wikipedia.org/wiki/Knapsack_problem#0.2F1_Knapsack_Problem)
// Given a set `[{weight:Number, benefit:Number}]` and a capacity,
// find the maximum value possible while keeping the weight below
// or equal to the capacity
// **params**:  
//    `capacity`  : Number,  
//    `items`     : [{w:Number, b:Number}]  
// **returns**:  
//    An object containing `maxValue` and `set`
function knapsack(items, capacity) {
  var idxItem   = 0,
      idxWeight = 0,
      oldMax    = 0,
      newMax    = 0,
      numItems  = items.length,
      weightMatrix  = new Array(numItems+1),
      keepMatrix    = new Array(numItems+1),
      solutionSet   = [];

  // Setup matrices
  for(idxItem = 0; idxItem < numItems + 1; idxItem++){
    weightMatrix[idxItem] = new Array(capacity+1);
    keepMatrix[idxItem]   = new Array(capacity+1);
  }

  // Build weightMatrix from [0][0] -> [numItems-1][capacity-1]
  for (idxItem = 0; idxItem <= numItems; idxItem++){
    for (idxWeight = 0; idxWeight <= capacity; idxWeight++){

      // Fill top row and left column with zeros
      if (idxItem === 0 || idxWeight === 0){
        weightMatrix[idxItem][idxWeight] = 0;
      }

      // If item will fit, decide if there's greater value in keeping it,
      // or leaving it
      else if (items[idxItem-1].w <= idxWeight){
        newMax = items[idxItem-1].b + weightMatrix[idxItem-1][idxWeight-items[idxItem-1].w];
        oldMax = weightMatrix[idxItem-1][idxWeight];

        // Update the matrices
        if(newMax > oldMax){ 
          weightMatrix[idxItem][idxWeight]  = newMax;
          keepMatrix[idxItem][idxWeight]    = 1;
        }
        else{
          weightMatrix[idxItem][idxWeight]  = oldMax; 
          keepMatrix[idxItem][idxWeight]    = 0;
        }
      }

      // Else, item can't fit; value and weight are the same as before
      else{
        weightMatrix[idxItem][idxWeight] = weightMatrix[idxItem-1][idxWeight];
      }
    }
  }

  // Traverse through keepMatrix ([numItems][capacity] -> [1][?])
  // to create solutionSet
  idxWeight = capacity;
  idxItem   = numItems;
  for(idxItem; idxItem > 0; idxItem--){
    if(keepMatrix[idxItem][idxWeight] === 1){
      solutionSet.push(items[idxItem - 1]);
      idxWeight = idxWeight - items[idxItem - 1].w;
    }
  }
  return {"maxValue": weightMatrix[numItems][capacity], "set": solutionSet};
}

exports = knapsack;

bug on line 29

  for (idxItem = 0; idxItem <= numItems; idxItem++){
    for (idxWeight = 0; idxWeight <= capacity; idxWeight++){

should be:

  for (idxItem = 0; idxItem <= numItems+1; idxItem++){
    for (idxWeight = 0; idxWeight <= capacity+1; idxWeight++){

you forgot to add 1 since you are creating a 0 col and row

Is there any licence attached to this? I would like to be able to use it in my project if you don't mind, but that isn't possible under the default licence.

Thanks for your solution , i used it.sounds great

@alxngyn

Your suggested correction:

for (idxItem = 0; idxItem <= numItems+1; idxItem++){
for (idxWeight = 0; idxWeight <= capacity+1; idxWeight++){

results in the following error:

https://repl.it/repls/GregariousInvolvedLock

TypeError: Cannot set property '0' of undefined
at knapsack (evalmachine.:34:42)
at evalmachine.:76:1
at Script.runInContext (vm.js:133:20)
at Object.runInContext (vm.js:311:6)
at evaluate (/run_dir/repl.js:133:14)
at ReadStream. (/run_dir/repl.js:116:5)
at ReadStream.emit (events.js:198:13)
at addChunk (_stream_readable.js:288:12)
at readableAddChunk (_stream_readable.js:269:11)
at ReadStream.Readable.push (_stream_readable.js:224:10)