Four ways to solve this problem:
- Recursion
- DP
- Memoization
- DP space optimised
function knapSack(W, items, n) {
// making and initializing dp array
var dp = Array(W + 1).fill(0);
for (let i = 1; i < n + 1; i++) {
for (let w = W; w >= 0; w--) {
const item_weight = items[i - 1].weight;
const item_value = items[i - 1].value;
if (item_weight <= w)
// finding the maximum value
dp[w] = Math.max(dp[w], dp[w - item_weight] + item_value);
}
}
return dp[W]; // returning the maximum value of knapsack
}
// Driver code
const items = [
{ value: 60 , weight: 10},
{ value: 100, weight: 20},
{ value: 120, weight: 30}
];
var capacity = 50;
var n = val.length;
console.log(knapSack(capacity, items, n));