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