Skip to content

Instantly share code, notes, and snippets.

@jinwolf
Created January 5, 2016 19:54
Show Gist options
  • Select an option

  • Save jinwolf/33af666c8882dfd5a6b0 to your computer and use it in GitHub Desktop.

Select an option

Save jinwolf/33af666c8882dfd5a6b0 to your computer and use it in GitHub Desktop.
(JavaScript) Knapsack problem in a recursive way
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(types, capacity) {
var maxValuesAtCapacities = new Array(capacity + 1);
return getMaxValueAtCapacity(capacity);
function getMaxValueAtCapacity(capacity) {
if (capacity < 1) {
return 0;
}
var maxValueAtCurrentCapapcity = 0;
if (maxValuesAtCapacities[capacity]) {
return maxValuesAtCapacities[capacity];
} else {
types.forEach(function(cake) {
if (cake.weight <= capacity) {
var cakeTotalValue = cake.value + getMaxValueAtCapacity(capacity - cake.weight);
maxValueAtCurrentCapapcity = Math.max(maxValueAtCurrentCapapcity, cakeTotalValue);
}
});
}
//console.log(maxValueAtCurrentCapapcity);
maxValuesAtCapacities[capacity] = maxValueAtCurrentCapapcity;
return maxValueAtCurrentCapapcity;
}
}
console.log(getMaxValue(cakeTypes, 20));
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment