This is my javascript implementation for the knapsack problem. In this problem, you are given a list of items with weights and values, and a knapsack with a weight capacity. The object is to determine how to maximize the value of objects you can hold in the knapsack without exceeding the weight capacity. My function below takes two parameters, items (an array of item objects, each containing a weight and value field, and a capacity integer representing the knapsack weight capacity. I use a memo table in which each index:weight is stored for repeated access to avoid duplicate calculations of getMax(). Is my implementation good? Can it be improved?
function knapsackMaxValue(items, capacity) {
const memo = {}
function getMax(i, weight) {
if (i == items.length) {
return 0;
}
if (memo[i + ':' + weight] != undefined) {
console.log('memo found')
return memo[i + ':' + weight]
}
if (items[i].weight + weight > capacity) {
memo[i + ':' + weight] = getMax(i + 1, weight)
return memo[i + ':' + weight]
} else {
let maxValue = Math.max(getMax(i + 1, weight), items[i].value + getMax(i + 1, weight + items[i].weight))
memo[i + ':' + weight] = maxValue
return maxValue
}
}
return getMax(0, 0)
}