Knapsack problem with Duplicate items in JavaScript
Given two integer arrays val representing the value of each item and wt representing the weight of each item, along with an integer W which represents the maximum weight capacity of the knapsack, determine the maximum value that can be achieved within the given weight limit when an unlimited number of copies of each item can be included in the knapsack.
Example:
Input: val = [10, 40, 50, 70];
wt = [1, 3, 4, 5];
W = 8;
Output: 110
Below are the approaches to solve the Knapsack problem with Duplicate items using JavaScript:
Table of Content
- Using Dynamic Programming Approach
- Using Greedy Approach
Using Dynamic Programming Approach
We define a 2D array dp where dp[i][j] represents the maximum value that can be obtained using the first i items and a knapsack with capacity j. We iterate through each item and each capacity, and for each item, we consider whether to include it or not. If we include the item, we update the value in dp accordingly.
Example: The example below shows the knapsack problem with duplicate items using dynamic programming in JavaScript
function knapsackDynamic(w, v, c) {
const n = w.length;
const dp = new Array(n + 1).fill(0)
.map(() => new Array(c + 1).fill(0));
for (let i = 1; i <= n; i++) {
for (let j = 1; j <= c; j++) {
if (w[i - 1] <= j) {
dp[i][j] = Math.max(dp[i - 1][j],
dp[i][j - w[i - 1]]
+ v[i - 1]);
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
return dp[n][c];
}
const w = [2, 3, 4, 5];
const v = [3, 7, 2, 9];
const c = 5;
console.log(knapsackDynamic(w, v, c));
Output
10
Time Complexity: O(n * capacity), where n is the number of items.
Space Complexity: O(n * capacity).
Using Greedy Approach
The function knapsackGreedy takes three parameters, weights, values, and capacity. It calculates the value-to-weight ratios for each item and stores them along with their indices in an array. The ratios array is then sorted in descending order based on the value-to-weight ratios. It iterates over the sorted ratios array, selecting items in decreasing order of their value-to-weight ratios, and adds their values to the knapsack as long as the capacity allows. The function returns the total value of items selected for the knapsack.
Example: The example below shows the knapsack problem with duplicate items using a greedy approach in JavaScript.
function knapsackGreedy(w, v, c) {
const n = w.length;
const r = [];
for (let i = 0; i < n; i++) {
r.push({
index: i, ratio: v[i]
/ w[i]
});
}
r.sort((a, b) => b.ratio - a.ratio);
let totalValue = 0;
for (let i = 0; i < n && c > 0; i++) {
const itemIndex = r[i].index;
if (w[itemIndex] <= c) {
totalValue += v[itemIndex];
c -= w[itemIndex];
}
}
return totalValue;
}
const weights = [2, 3, 4, 5];
const values = [3, 7, 2, 9];
const capacity = 5;
console.log(knapsackGreedy(weights, values, capacity));
Output
10
Time Complexity: O(n log n), where n is the number of items.
Space Complexity: O(n).