Fractional Knapsack Problem

You might have heard about Knapsack Problem but find it difficult to Implement it?
Then you are on right post. Today you are gonna learn what is Fractional Knapsack Problem in an easy way.So let's get started.

What does Knapsack Problem say?
Statement: You have being given a bag of capacity C.Where in if you try to add extra weight then the Bag will burst i.e total weight < = C. You have given n  items of individual weights and have some different profit.Your job is to insert items in the bag such that the profit is maximum.

Special case:  if the weight of the item is greater than the capacity of the bag then the items can be placed in the bag partially.

let's see an example,
The capacity C of bag is 70. and the items are given in the following table along with the profit and weight associated with it.

ITEM NO	WEIGHT	PROFIT
1	50	100
2	20	100
3	30	90
4	10	80

 step 1:Evaluate the vale of PROFIT/WEIGHT ratio.

ITEM NO	WEIGHT	PROFIT	PROFIT/WEIGHT
1	50	100	2
2	20	100	5
3	30	90	3
4	10	80	8

 step 2:Arrange in descending order of PROFIT/WEIGHT ratio.

ITEM NO	WEIGHT	PROFIT	PROFIT/WEIGHT
4	10	80	8
2	20	100	5
3	30	90	3
1	50	100	2

 let profit=0, C =70(given).

keep on adding items in the mentioned order in table 3. such that

weight of item<capacity of bag at that point(C)

As an item is added the capacity decreases and the profit increases.

As 10<70

profit=80; capcity=capacity-weight of item added.

C=70-10=60;

as 20<60

C=60-20=40

profit=180;

as 30<40

profit=270;

C=40-30=10;

now 50>10

if the weight of the item is greater than the capacity of the bag then the partial part of item is added in the bag.

profit= profit+(capacity of bag/weight of object) *profit of that item.

C=0;

profit=profit+(10/50)*100;

         =290

hence the total profit(max ) earned is 290

This was the Fractional Knapsack problem .

hope you understood the concept well.

FOR SOLUTION PROGRAM  of  Fractional Knapsack please refer my post
Solution to Fractional Knapsack.