Why Fractional Knapsack Problem in DSA Typescript?

The Big Idea

What if you could take just the right part of each item to get the most value in your bag?

The Scenario

Imagine you have a backpack with limited space and many items to carry. Each item has a weight and a value. You want to fill your backpack to get the most value possible. But if you try to pick items one by one without a plan, you might fill the bag with heavy, low-value items and miss out on better choices.

The Problem

Trying to pick items manually is slow and confusing. You might pick heavy items first and run out of space quickly. It's easy to make mistakes and miss the best combination. Also, if you can only take whole items, you might waste space that could be used for parts of valuable items.

The Solution

The Fractional Knapsack Problem lets you take parts of items, not just whole ones. By sorting items by value per weight and taking the best parts first, you fill your backpack with the highest value possible. This method is fast, simple, and guarantees the best result.

Before vs After

✗ Before

let totalWeight = 0;
let totalValue = 0;
for (let item of items) {
  if (totalWeight + item.weight <= maxWeight) {
    totalWeight += item.weight;
    totalValue += item.value;
  }
}

✓ After

items.sort((a, b) => (b.value / b.weight) - (a.value / a.weight));
let totalWeight = 0;
let totalValue = 0;
for (let item of items) {
  if (totalWeight + item.weight <= maxWeight) {
    totalWeight += item.weight;
    totalValue += item.value;
  } else {
    let remain = maxWeight - totalWeight;
    totalValue += item.value * (remain / item.weight);
    break;
  }
}

What It Enables

This concept lets you maximize value by smartly choosing whole or parts of items to perfectly fill your limited space.

Real Life Example

Imagine packing snacks for a trip with a small bag. You want to carry the tastiest and most energy-packed snacks. Fractional Knapsack helps you decide how much of each snack to pack to get the best energy without overloading your bag.

Key Takeaways

Manual picking wastes space and value.

Fractional Knapsack sorts items by value per weight.

It allows taking parts of items for maximum value.