Why Fractional Knapsack Problem in DSA C?

The Big Idea

What if you could carry the most valuable mix by taking just parts of items instead of whole ones?

The Scenario

Imagine you have a backpack that can carry a limited weight, and you want to fill it with items to get the most value. You try to pick whole items one by one, but some items are too heavy or too valuable to skip. How do you decide what to take?

The Problem

Picking items one by one without breaking them can leave a lot of unused space in your backpack. You might miss out on getting more value because you can't take part of an item. Doing this by hand is slow and often leads to poor choices.

The Solution

The Fractional Knapsack Problem lets you take parts of items instead of whole items. This way, you can fill your backpack perfectly to get the highest total value. It uses a simple rule: take items with the best value per weight first, even if only partially.

Before vs After

✗ Before

int totalValue = 0;
for (int i = 0; i < n; i++) {
    if (weight[i] <= capacity) {
        totalValue += value[i];
        capacity -= weight[i];
    }
}

✓ After

sortItemsByValuePerWeight();
for (int i = 0; i < n && capacity > 0; i++) {
    int take = (weight[i] < capacity) ? weight[i] : capacity;
    totalValue += take * valuePerWeight[i];
    capacity -= take;
}

What It Enables

This concept allows you to maximize the total value you carry by smartly choosing whole or parts of items based on their value-to-weight ratio.

Real Life Example

Think about packing a lunchbox with snacks. Some snacks can be split (like nuts or candies), so you take just enough to fill the box and get the tastiest mix possible.

Key Takeaways

Manual picking wastes space and value.

Fractional Knapsack lets you take parts of items for best value.

It sorts items by value per weight and fills the capacity greedily.