Fractional Knapsack Problem in C++ | Greedy Algorithm

Before writing this code, you must understand what is the Greedy algorithm and Fractional Knapsack problem.

Greedy Algorithm

Consider you want to buy a car-the one with 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 brand for the car and filter out all the infamous brand which do not produce good quality cars. Now search and compare the good brand cars which give high performance. In this way, you are again filtering out cars which do not perform well in the market.

By doing this, your task becomes easier and the chance of getting your desired car has increased.

What you just did is called Greedy approach. By greedy approach you sort or filter data in such a way that you doesn’t have to compare or analyze every data to solve your problem. You just look for only those data which are relevant and useful to you.

Fractional Knapsack Problem

Suppose you are given 10 types of vegetables which weigh different and the total weight of 10 vegetables is around 25 kg. But you have a bag which can hold only 10 kg of vegetables. Here 10 kg limit is known as Knapsack bag or weight.

How will you choose the vegetables for your bag?

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

But there can be a problem.

The vegetables which have high nutrient value can weigh more than other vegetables, due to which you 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 and sort the vegetable in order of decreasing nutrient-value / weight ratio (which you can call density). And from the top take until your bag is full.

In this way, you don’t need to compare vegetable because you already sorted the array and don’t even have to look at those vegetables which are at the end of low nutrient-value / weight value (Only if your bag is full).

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 on 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 ( W is Knapsack weight).

The most important point is that we can take the fraction of weight for the last item to make our bag completely full if the adding item’s total weight exceed W. That’s why its called fractional knapsack problem.

Fractional Knapsack Problem C++ code

Output

Fractional Knapsack Problem

Online Compiler

If you have any problem then comment below.

Also check:

Dynamic 2D array in C++.

Swap two variables in C++ without using third variable.

admin

I am a B.tech IT Student from India. Technology and programming is the most enthusiastic thing for me in this world. I like learning new techniques and use them for real-world application because I feel tech is future. Let's learn and grow TOGETHER.