-
-
Save danwoods/7496329 to your computer and use it in GitHub Desktop.
//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; |
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
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)
bug on line 29
should be:
you forgot to add 1 since you are creating a 0 col and row