Introduction

Have you ever been in a situation where you need to pick the best candies with a limited bag size? Imagine you’re at a candy shop, and you have a small backpack that can only carry up to 10kg. You want to grab the most delicious (and expensive) candies, but some are heavier than others. What would be your strategy?

This scenario is similar to a well-known problem in computer science called the Knapsack Problem. Let’s dive into it!

What is the Knapsack Problem?

In the knapsack problem, you have a collection of items, and each item has two things:

Weight (how heavy it is)
Value (how valuable or useful it is)

The goal is to pick items to maximize the value you carry, without exceeding the weight limit of the knapsack (your bag).

Two Versions of the Problem

0/1 Knapsack: You either take the whole item or leave it (you can’t break an item).
Fractional Knapsack: You can take parts of an item. For example, if an item weighs 5kg, and you only have space for 2kg, you can take 2/5 of that item.

In this post, we’ll focus on the Fractional Knapsack Problem, where you can break items and take fractions of them to maximize the total value. And to solve it, we’ll use something called a Greedy Algorithm.

Breaking Down the Problem

The Objective

You have a list of n items, each with a specific weight and value. Your task is to fill a knapsack with a maximum weight capacity W, such that the total value you carry is as high as possible.

The Trick: Maximize Value-to-Weight Ratio

In the fractional knapsack problem, the best approach is to pick items that give you the most value for the least weight. This is known as value-to-weight ratio.

If one item has a value of 100 and a weight of 2kg, its ratio is 100/2 = 50.
Another item with a value of 50 and weight of 2kg has a ratio of 50/2 = 25.

Obviously, the first item gives you more “value per kilogram,” so you’d want to prioritize it.

The Algorithm

Here’s how we solve the fractional knapsack problem:

Sort the items by value-to-weight ratio in descending order (highest ratio first).
Start filling the knapsack with the item that has the highest ratio.
If you can’t fit the entire item, take only the fraction that fits in the remaining space.

To do this efficiently, we can represent each item as a structure in C++ and sort them using a comparison function.

C++ Code for Fractional Knapsack

Let’s see how we can implement this algorithm in C++.

Step 1: Structure to Represent Items

We’ll define a structure Item to hold the value and weight of each item.

struct Item {
    int value, weight;
};

Step 2: Custom Comparison Function

We need to sort items based on their value-to-weight ratio. For that, we can write a comparison function:

bool cmp(Item a, Item b) {
    double r1 = (double)a.value / a.weight;
    double r2 = (double)b.value / b.weight;
    return r1 > r2;
}

This function will return true if the ratio of item a is greater than that of item b. We will use this to sort the items in decreasing order of their value-to-weight ratio.

Step 3: Main Function

Now, let’s write the fractionalKnapsack function to solve the problem.

double fractionalKnapsack(int W, Item arr[], int n) {
    // Sort items based on value-to-weight ratio
    sort(arr, arr + n, cmp);
double totalValue = 0.0; // Total value in knapsack
    for (int i = 0; i < n; i++) {
        // If the item can fully fit into the knapsack
        if (arr[i].weight <= W) {
            W -= arr[i].weight;
            totalValue += arr[i].value;
        }
        // If the item cannot fully fit, take the fraction of it
        else {
            totalValue += arr[i].value * ((double)W / arr[i].weight);
            break;
        }
    }

    return totalValue;
}

Step 4: Example Usage

Let’s say we have three items:

Item 1: Value = 60, Weight = 10
Item 2: Value = 100, Weight = 20
Item 3: Value = 120, Weight = 30

And the knapsack can hold a maximum weight of 50.

int main() {
    Item arr[] = {{60, 10}, {100, 20}, {120, 30}};
    int W = 50;
    int n = sizeof(arr) / sizeof(arr[0]);
cout << "Maximum value we can obtain = " << fractionalKnapsack(W, arr, n);
    return 0;
}

This will output

Maximum value we can obtain = 240

How does it work? The algorithm takes the full first and second items, and only a fraction of the third item, maximizing the value carried in the knapsack.

Explaining the Code

Sorting: We first sort the items based on their value-to-weight ratio using the cmp function.
Filling the Knapsack: The loop checks if an item can fit in the knapsack. If it does, we take the whole item. Otherwise, we take only the fraction that fits and then stop.
Result: The total value in the knapsack is stored in the totalValue variable.

Conclusion

The Fractional Knapsack Problem is a great example of using a greedy algorithm to maximize the value you can carry. By sorting the items based on their value-to-weight ratio and filling the knapsack with the most valuable items first, you can quickly arrive at the best solution.

If you enjoyed this algorithm, try implementing it yourself in C++, and even experiment with different sets of items! And if you’re feeling adventurous, look up the 0/1 Knapsack Problem and see how it compares.

Understanding the Fractional Knapsack Problem