Summary: In this tutorial, we will learn what Fractional Knapsack Problem is and how to solve fractional knapsack problem using Greedy algorithm in C++ and Java.

What is the Greedy Algorithm?

Consider you want to buy a car – one having the best features whatever the cost may be.

What will you do?

If you start looking and comparing each car in the world. It will take a lot of time.

The best way is to shortlist the best car’s brand and filter out all the infamous ones that do not produce good quality cars.

Next, you would filter the cars based on their performance.

By doing this, your task becomes easier i.e. the chances of getting your desired car have increased.

This approach of solving our problem is known as Greedy approach.

In the greedy approach, we sort or filter data in such a way that we don’t have to compare or analyze every data to solve our problem. We just care for those data which are relevant and useful to us.

Introduction to Fractional Knapsack Problem

Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible

Wikipedia

For example, suppose you are given 10 types of vegetables which weigh different and the total weight of 10 vegetables is around 25 kg. You have a bag that can hold a maximum of 10 kg of vegetables.

HereĀ 10 kg limit is also known as Knapsack bag or Knapsack weight.

How will you choose the vegetables for your bag?

Definitely, you will choose vegetables that are fresh or has more nutrient value.

But there can be a problem.

The vegetables which have high nutrient value can weigh more than low nutritional vegetables, due to which you will have to carry fewer vegetables in your 10 kg capacity bag.

What to do now?

Since you want vegetables with high nutrient value and less weight, so that you can accommodate more vegetables in your bag, you are likely to follow this rule.

 vegetable ~ nutrient-value

vegetable ~ 1/weight

which combines to

vegetable ~ nutrient-value / weight

Thus, the best way is to use a greedy approach i.e. sort the vegetables in order of decreasing nutrient-value / weight ratio (which you can call density) and take the vegetables with higher ratio value until the bag is full.

In this way, you don’t have to compare vegetables because you have already sorted them based on the nutrient-value/weight ratio. You don’t even have to look at those vegetables which are at the lower end of the nutrient-value/weight value (except if your bag is not full).

The most important point is that we can take the fraction of the last item to completely fill our bag (if adding a whole item exceeds W). That’s why its called a fractional knapsack problem.

Fractional Knapsack Problem Solution in C++ and Java

The same approach we are using in our program.

  • We have taken an array of structures named Item.
  • Each Item has value & weight.
  • We are calculating density= value/weight for each item and sorting the items array in the order of decreasing density.
  • We add values from the top of the array to totalValue until the bag is full i.e. totalValue<=W ( where W is Knapsack weight).

Here is the implementation of the above knapsack problem in C++ and Java.

C++

Java

Output:

Fractional Knapsack Problem

In this tutorial, we learned what the greedy algorithm and the fractional knapsack problem are. We also learned how to solve the Fractional Knapsack problem using the Greedy algorithm in C++ and Java.

Leave a Reply