Fractional Knapsack Problem

Given the weights and profits/values of N items, put these items in a knapsack of capacity W to get the maximum total profit in the knapsack. In Fractional Knapsack, we can break items into fractions for maximizing the total value.

Greedy Approach

The naive approach of exploring all subsets of items takes O(2^N) time.

The optimal greedy strategy is to calculate the value-to-weight ratio (value / weight) for each item, sort them in descending order of this ratio, and iteratively add items into the knapsack:

1. Calculate the ratio (value / weight) for each item.
2. Sort all items in descending order of their ratio.
3. Initialize the total value obtained (totalValue = 0) and remaining capacity (capacity = W).
4. Iterate through the sorted items:
   • If the weight of the item is less than or equal to the remaining capacity, take the whole item:
     • Add its full value to totalValue.
     • Subtract its full weight from capacity.
   • If the item is heavier than the remaining capacity, take a fraction:
     • Add the fraction value: remaining capacity * (item value / item weight) to totalValue.
     • Break the loop (knapsack is now full).
5. Return totalValue.

Examples

Example 1

• Input: Items = [{ val: 60, wt: 10 }, { val: 100, wt: 20 }, { val: 120, wt: 30 }], Capacity W = 50
• Ratios: Item 1 = 6.0, Item 2 = 5.0, Item 3 = 4.0
• Selection:
  • Take Item 1 (weight 10, remaining capacity = 40, value = 60).
  • Take Item 2 (weight 20, remaining capacity = 20, value = 60 + 100 = 160).
  • Take fraction of Item 3 (take 20 out of 30 weight, value = 160 + 20 * 4.0 = 240).
• Output: 240

Example 2

• Input: Items = [{ val: 500, wt: 30 }], Capacity W = 10
• Ratios: Item 1 = 16.67
• Selection: Take fraction of Item 1 (take 10 out of 30 weight, value = 10 * 16.667 = 166.667).
• Output: 166.667

JavaScript Code Implementation

class Item {
    constructor(value, weight) {
        this.value = value;
        this.weight = weight;
    }
}
 
function fractionalKnapsack(W, items) {
    // 1. Sort items in descending order of value/weight ratio
    items.sort((a, b) => {
        const r1 = a.value / a.weight;
        const r2 = b.value / b.weight;
        return r2 - r1; // Descending
    });
 
    let currentWeight = 0;
    let totalValue = 0.0;
 
    // 2. Iterate through sorted items
    for (let item of items) {
        // If adding item doesn't overflow, add it completely
        if (currentWeight + item.weight <= W) {
            currentWeight += item.weight;
            totalValue += item.value;
        } 
        // If it overflows, take the fraction of it
        else {
            const remaining = W - currentWeight;
            totalValue += item.value * (remaining / item.weight);
            break; // Knapsack is full
        }
    }
 
    return totalValue;
}
 
// Driver code matching Example 1
const items1 = [
    new Item(60, 10),
    new Item(100, 20),
    new Item(120, 30)
];
const W1 = 50;
console.log("Max value in knapsack:", fractionalKnapsack(W1, items1));
// Output: Max value in knapsack: 240
 
// Driver code matching Example 2
const items2 = [
    new Item(500, 30)
];
const W2 = 10;
console.log("Max value in knapsack:", fractionalKnapsack(W2, items2).toFixed(3));
// Output: Max value in knapsack: 166.667

Complexity Analysis

• Time Complexity: O(N log N)
  • Sorting the items by ratio takes O(N log N) time.
  • The loop to select items takes O(N) time.
• Auxiliary Space: O(1)
  • If sorting is performed in-place on the inputs.