Skip to content

Instantly share code, notes, and snippets.

@jinwolf
Created January 5, 2016 01:48
Show Gist options
  • Save jinwolf/c11827b9f89552782e3c to your computer and use it in GitHub Desktop.
Save jinwolf/c11827b9f89552782e3c to your computer and use it in GitHub Desktop.
(JavaScript) Knapsack problem
function CakeType(weight, value) {
this.weight = weight;
this.value = value;
}
var cakeTypes = [
new CakeType(7, 160),
new CakeType(3, 90),
new CakeType(2, 15),
];
function getMaxValue(cakeTypes, capacity) {
// it's to cache the previous max results at each level
var maxValuesAtCurrentCaps = new Array(capacity + 1);
for (var currentCap = 0; currentCap <= capacity; currentCap++) {
var maxValueAtCurrentCap = 0;
cakeTypes.forEach(function(cakeType, index) {
if (cakeType.weight === 0 && cakeType.value === 0) {
throw new Error('Infinity');
}
if (cakeType.weight <= currentCap) {
maxValueAtCurrentCap = Math.max(maxValueAtCurrentCap, cakeType.value + maxValuesAtCurrentCaps[currentCap - cakeType.weight]);
}
});
maxValuesAtCurrentCaps[currentCap] = maxValueAtCurrentCap;
}
return maxValueAtCurrentCap;
}
console.log(getMaxValue(cakeTypes, 6));
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment