How to use Greedy Method In Javascript

Using Dynamic Programming

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.

JavaScript

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)

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