Fractional Knapsack Problem using JavaScript
In the fraction knapsack problem, we are given a set of items, each with a weight and a value, and a knapsack with a maximum weight capacity. We have to put items such that we can gain maximum profit i.e. put a most valuable combination of items in knapsack without exceeding the maximum weight capacity of the knapsack.
Different approaches to solving the fractional knapsack problem using JavaScript are as follows:
Table of Content
- Using Greedy Method
- Using Dynamic Programming
Using Greedy Method
We will Create a class Item to represent each item in the problem. Now we will Sort the items by their value-to-weight ratio in non-increasing order. Now, iterate through the sorted items list and check if adding the whole item will exceed the knapsack’s capacity, if it exceeds the capacity then take a fraction of the item that fits into the knapsack. Then update the total value and remaining capacity. Return total maximum value obtained.
Example: To demonstrate the fractional knapsack problem using a greedy approach.
class Item {
constructor(weight, value) {
this.weight = weight;
this.value = value;
this.ratio = value / weight;
}
}
function fractionalKnapsack(items, capacity) {
items.sort((a, b) => b.ratio - a.ratio);
let totalValue = 0;
let remainingCapacity = capacity;
for (let i = 0; i < items.length; i++) {
if (remainingCapacity <= 0)
break;
const currentItem = items[i];
const fraction = Math
.min(1, remainingCapacity / currentItem.weight);
totalValue += fraction * currentItem.value;
remainingCapacity -= fraction * currentItem.weight;
}
return totalValue.toFixed(2);
}
const items = [
new Item(10, 60),
new Item(20, 100),
new Item(30, 120)
];
const capacity = 50;
console.log(`Maximum value that can be obtained is`,
fractionalKnapsack(items, capacity));
Output
Maximum value that can be obtained is 240.00
Time Complexity: O(n log n + n). O(n log n )
Space Complexity: O(1)
Using Dynamic Programming
We will first Create a class Item with properties weight and value. Create a function fractionalKnapsackDynamic Function and create a dp array of size capacity + 1, the initially filled with zero. Now we Iterate from 1 to capacity and for each capacity, iterate through each item and Update dp[i] with the maximum value achieved for the current capacity. return dp[capacity] , contain maximum profit achieved.
Example: To demonstrate a fractional knapsack problem using dynamic programming approach.
class Item {
constructor(weight, value) {
this.weight = weight;
this.value = value;
}
}
function fractionalKnapsackDynamic(items, capacity) {
const n = items.length;
const dp = new Array(capacity + 1)
.fill(0);
for (let i = 1; i <= capacity; i++) {
let maxValue = 0;
for (let j = 0; j < n; j++) {
if (items[j].weight <= i) {
maxValue = Math
.max(maxValue, dp[i - items[j].weight] + items[j].value);
}
}
dp[i] = maxValue;
}
return dp[capacity];
}
const items = [
new Item(10, 60),
new Item(20, 100),
new Item(30, 120)
];
const capacity = 50;
console.log(`Maximum value obtained using dynamic approach is`,
fractionalKnapsackDynamic(items, capacity));
Output
Maximum value obtained using dynamic approach is 300
Time Complexity: O(n * capacity)
Space Complexity: O(capacity)