How to solve a fractional Knapsack Problem using the Greedy method?

The fractional knapsack problem is a well-known problem in combinatorial optimization and computer science. The problem can be stated as follows: given a set of items, each with a weight and a value, and a knapsack with a weight limit, what is the most valuable subset of items that can be fit into the knapsack? The problem can be further constrained to require that the items be selected in a certain order, or to allow for multiple copies of each item.

From the name itself, it is clearly understandable that in a fractional knapsack problem we can select a fractional part of an element. Whereas if it is a 0/1 knapsack, then we can either select the whole item or can select nothing.

For example, see the template of this article. If you’re given a plate and some fruits and you’ve been said to serve 100 grams of fruits to your grandfather. Choose those fruits which have the maximum vitamins.

This problem could be a fractional knapsack problem.

The fractional knapsack problem is a classic example of the greedy algorithm design paradigm. That is, the problem can be solved by making a series of locally optimal choices, without regard for the overall optimality of the solution. In this case, the locally optimal choice is to always select the item with the highest value-to-weight ratio.

How to solve the Fractional Knapsack Problem?

The fractional knapsack problem can be solved using a simple greedy algorithm.

1. First, sort the items in descending order of value-to-weight ratio.
2. Then, starting with the most valuable item, add items to the knapsack until the weight limit is reached. If an item cannot be completely added to the knapsack (i.e. its weight is greater than the remaining weight limit), then add a fraction of the item so that the knapsack is filled to capacity. The value of the knapsack is then the sum of the values of the items plus the fractional value of the last item added.

The time complexity of the greedy algorithm is O(n log n), where n is the number of items. This is because the items must be sorted in descending order of value-to-weight ratio, which takes O(n log n) time. Once the items are sorted, the greedy algorithm runs in linear time, as it simply iterates over the items and adds them to the knapsack one at a time.

The greedy algorithm for the fractional knapsack problem is not guaranteed to find the optimal solution, but it will find a solution that is close to optimal. In fact, the greedy algorithm always produces a solution that is within a factor of two of the optimal solution. This is because the greedy algorithm makes the locally optimal choice at each step, and the value-to-weight ratio is a good proxy for the overall value of an item. Thus, the greedy algorithm will always select items with high value-to-weight ratios, and will always find a solution that is close to optimal.

The fractional knapsack problem can also be solved using dynamic programming. However, the dynamic programming solution is significantly more complicated than the greedy solution and is beyond the scope of this article.

So here is the code of the fractional knapsack problem

//solution of Fractional Knapsack using Greedy Algorithm
#include <stdio.h>

void fracKnapsack(float W, float wt[], float prof[], int n)
{
    int i, k;
    float fp = 0;

    for (i = 0; i < n; i++)
    {
        if (wt[i] > W)
            break;
        else
        {
            fp += prof[i];
            W -= wt[i];
        }
    }

    fp = fp + ((W / wt[i]) * prof[i]);

    printf("Maximum profit is: %f", fp);
}

int main(void)
{
    int n, i;
    float prof[100], wt[100], W, temp;
    float wp[100];
    printf("Capacity: ");
    scanf("%f", &W);
    printf("Total number of objects- ");
    scanf("%d", &n);
    printf("Weight & Corresponding profit-\n");
    for (i = 0; i < n; i++)
    {
        scanf("%f%f", &wt[i], &prof[i]);
      // We're finding (Profit/Weight) which will help us to sort the items
        wp[i] = prof[i] / wt[i];
        printf("P/W = %f\n", wp[i]);
    }
    for (i = 0; i < n; i++)
    {
      //Sorting items in descending order
        if (wp[i] < wp[i + 1])
        {
           	wp[i+1]=temp;
            wp[i] = wp[i+1];
            temp = wp[i];
        }
    }
    fracKnapsack(n, wt, prof, W);
}

Input:

Capacity: 15
Total number of objects- 7
Weight & Corresponding profit-
2
10
P/W = 5.000000
3
5
P/W = 1.666667
5
15
P/W = 3.000000
1
6
P/W = 6.000000
7
7
P/W = 1.000000
1
3
P/W = 3.000000
4
18
P/W = 4.500000

Output:

Maximum profit is: 21.000000

Read the comments and “How to solve” part to understand the code correctly.

Now if you’ve understood the code, I’ve two questions for you.

1. Why we’re doing “Profit/Weight” but not “Weight/profit”?
2. What will happen if we do “Weight/Profit” instead of “Profit/Weight”?

Comment below if you got the answer.

If you find this blog helpful, share it with your friends and ask them the last two questions. See if they can answer them.

See you soon in the next blog.