Skip to content

Instantly share code, notes, and snippets.

@mohammedri
Forked from danwoods/knapsack.js
Created May 16, 2016 14:27
Show Gist options
  • Save mohammedri/a8834c23b18ec38ad012de41706d9bda to your computer and use it in GitHub Desktop.
Save mohammedri/a8834c23b18ec38ad012de41706d9bda to your computer and use it in GitHub Desktop.
Knapsack algorithm in JavaScript
//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;
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment