Last active
January 4, 2017 17:04
-
-
Save Muzietto/66e3510d6bfdeb79f32ea21b880f29d2 to your computer and use it in GitHub Desktop.
A knapsack 0/1 algo that cycles first and foremost through the knapsack weights - clumsier but more logical
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
function knapsack01(maxWeight, items, returnAllKnapsacks) { | |
items = items.sort((a,b)=>a.weight-b.weight); | |
var knapsacks = new Array(maxWeight + 1); | |
for (var i = 0; i <= maxWeight; i++) { | |
knapsacks[i] = new Array(items.length); | |
for (var j = 0; j < items.length; j++) { | |
knapsacks[i][j] = 0; | |
}; | |
}; | |
for (var i = 1; i <= maxWeight; i++) { | |
for (var j = 0; j < items.length; j++) { | |
var curItem = items[j]; | |
if (curItem.weight > i) { | |
knapsacks[i][j] = (j === 0) ? 0 : knapsacks[i][j-1]; | |
continue; | |
} | |
var valueWithoutItem = (j === 0) ? 0 : knapsacks[i][j-1]; | |
var valueLeavingRoomForItem = (j === 0) ? 0 : knapsacks[i-curItem.weight][j-1]; | |
var valueWithItem = curItem.value + valueLeavingRoomForItem; | |
knapsacks[i][j] = Math.max(valueWithoutItem, valueWithItem); | |
} | |
} | |
return (returnAllKnapsacks) ? knapsacks : knapsacks[maxWeight][items.length-1]; | |
} |
Sample usage: knapsack01(8,[{value:1,weight:1},{value:4,weight:3},{value:5,weight:4},{value:7,weight:5}]);
The final version contains an optional parameter returnAllKnapsacks
, which is used by the sister function knapsackContents to retrieve which boxes are present in the composed knapsack.
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
The way dynamic programming is best understood is by cycling through problem states, starting with the simplest ones. In the case of a jumping frog you start from a zero-length jump and then cycle through longer and longer jumps.
Quirkly enough, in the case of knapsack 0/1, the easiest (and most bragged about on YouTube) algorithm appears to be one that cycles through the boxes and only afterwards through the possible knapsacks. But what about states? How is a student supposed to concoct such an algo when the teacher has been telling so far "focus on states first"?
So here is an algo that cycles through the knapsacks (starting with no knapsack at all) and for each knapsack tries all the boxes.
It may not be the most elegant, but it fits better with my learning style.