Knapsack Problem using Greedy method
Let us assume that we have n objects, here each object is having a
profit, where profit is represented by Pi . So P1 means first object
profit, P2 means second object profit and each object will have
corresponding weight also.
Weight is represented with the help of Wi.
We have a Knapsack here, Knapsack is nothing but a bag whose
weight is represented with the help of m.
Assume that the size of the Knapsack, that is the capacity of the bag is
20 kgs.
The main objective of Knapsack problem is to place the
corresponding objects in the bag with the minimum profit. That is, we
have to place all the objects in the Knapsack with the maximum
profit.
Here, an Optimal solution [Optimal solution means the best solution]
is represented with the help of Knapsack Vector and Knapsack Vector
is represented with the help of Xi.
Here, the value of Xi ranges from 0 to 1 i.e., 0 <= X i <= 1. That
means, minimum value is 0 and maximum value is 1 and in between
we can have some fractional values also.
If the object is placed in the Knapsack, then we can say that X i = 1,
whereas if an object is not placed in the Knapsack, then we say that X i
= 0.
Let Knapsack contains some space, but in the space it is not possible
to place the object. Let here the remaining size of the bag is 10 kgs,
whereas our object size is 30 kgs. So, we can’t place 30 kg of object
in 10kg of the bag. Then Xi can be calculated as.
Remaining ¿ Knapsack
Xi=
Actual Weight of the Object
The value of Xi may be 1 or 0 or some fraction value.
Objects 1 2 3 4 5 6 7
Profit 5 10 15 7 8 9 4
[P]
Weight 1 3 5 4 1 3 2
[W]
Weight = 15 ; n = 7
In the above problem we have 7 objects, with their Profits and
Weights. Total Weight, W = 15 kgs. Total objects n = 7.
We can assume that, we have one bag having weight 15 kgs or one
container having capacity 15 kgs.
Now, you have to select item such that you will get the maximum
profit. We cannot select all the items , because if you total the weight
of all the items then it would be greater than 15.
There are 3 approaches that we select the items where you will get the
maximum profit.
1. We can select the item first which is having maximum profit.
In the above problem, the maximum profit is 15, so that we can select
the item, then we will select 10 and so on.
2. We will select items having maximum weight, so that we can
select more and more items.
3. May be I can say that I will find out the ratio of profit by weight
and then I will select the items having maximum profit by
weight ratio as well.
In the above problem, the profit of item 3 is 15 you can say maximum
profit, but this profit is for 5 kgs, it is not for 1 kg. If you find out the
15
profit for 1kg, then profit would be 5
=3. So, for 1 kg it is 3.
So, the best approach is to find out the ratio profit by weight and then
select the item which is having the maximum profit by weight ratio.
Now, we will see all the three approaches and then we will compare
all the three approaches.
1. Select the item according to the maximum profit.
2. According to the minimum weight.
3. According to the maximum profit by weight ratio.
Approach 1: Select the items according to the maximum profit.
Total weight is 15 kgs.
Objects Profit [P] Weight [W] Remaining
Weight
3 15 5 15 – 5 = 10
2 10 3 10 – 3 = 7
6 9 3 7–3=4
5 8 1 4–1=3
4 3 21 3 3–3=0
7X 4 = 4 =
5.25
Total Profit = 47.25
Now, check out which item is having maximum profit which is 15 in
this case. Then Object is 3; Profit = 15; Weight = 5; Remaining
Weight = 15 – 5 =10.
Next, maximum profit Object = 2; Profit = 10; Weight = 3;
Remaining Weight = 10 – 3 = 7.
Next, maximum profit Object = 6; Profit = 9; Weight = 3; Remaining
Weight = 7 – 3 = 4.
Next, maximum profit Object = 5; Profit = 8; Weight = 1; Remaining
Weight = 4 – 1 = 3.
Next, maximum profit Object = 4 ; Profit = 7; Weight = 4
In this, Remaining Weight = 3, so we cannot select the complete
object, we cannot pick the complete object.
As we have to use Fractional Knapsack problem, so, we have to select
fraction of the object.
For example, suppose we have 4 kg of apple then you will select 3 kg
of apple, the remaining capacity is only 3.
So, out of 4 the weight you will select is 3. The profit would be
according to this 3, because we have selected this 3 and this Profit = 7
for Weight = 4 kgs.
So, you have to find out profit for 3 kgs and that profit would be 7 X
3 21
4
= 4
= 5.25. Now, Remaining Weight = 3 – 3 = 0. So, Remaining
Weight = 0 in the last.
Check out what is the total profit, here the total profit is 47.25
Approach 2 : Choose the item according to their Minimum Weight.
Total Weight is 15 kgs
Objects Profit [P] Weight [W] Remaining
Weight
1 5 1 15 – 1 = 14
5 8 1 14 – 1 = 13
7 4 2 13 – 2 = 11
2 10 3 11 – 3 = 8
6 9 3 8–3=5
4 7 4 5–4=1
3 1 1 1–1=0
15 x 5 =3
Total Profit = 46
Min. Weight = 1; Object = 1; Profit = 5; Weight = 1; Remaining
Weight = 15 - 1 = 14
Min. Weight = 1; Object = 5; Profit = 8; Weight = 1; Remaining
Weight = 14 - 1 = 13
Min. Weight = 2; Object = 7; Profit = 4; Weight = 2; Remaining
Weight = 13 - 2 = 11
Min. Weight = 3; Object = 2; Profit = 10; Weight = 3; Remaining
Weight = 11 - 3 = 8
Min. Weight = 3; Object = 6; Profit = 9; Weight = 3; Remaining
Weight = 8 - 3 = 5
Min. Weight = 4; Object = 4; Profit = 7; Weight = 4; Remaining
Weight = 5 - 4 = 1
Min. Weight = 5; Object = 3; Now, Remaining Weight = 1 and the
Total Weight = 5, so, we cannot select the complete object.
1
You will select the fraction of this object is 3 that is 5 , so, we will
1
select only 1 kg out of 5 kgs and this Profit is 15 x 5 = 3; Remaining
Weight = 1 – 1 = 0.
Finally, Remaining Weight = 0 and we cannot select any more item.
Total Profit is 46.
Approach 3 : We will find out the ratio of Profit by Weight and then
we will select the maximum Profit by Weight ratio.
Objects 1 2 3 4 5 6 7
Profit 5 10 15 7 8 9 4
[P]
Weight 1 3 5 4 1 3 2
[W]
P/W 5 3.3 3 1.75 8 3 2
We have to find out the Profit divided by Weight ratio.
For 1kg you will find out the Profit.
Profit = 5; Weight = 1; Profit / Weight = 5 [As it is for 1 kg]
Profit = 10; Weight = 3; Profit / Weight = 3.3 [As it is for 3 kg for 1
kg then Profit is 10 / 3 = 3.33]
Profit = 15; Weight = 5; Profit / Weight = 15 / 5 = 3
Profit = 7; Weight = 4; Profit / Weight = 7 / 4 = 1.75
Profit = 8; Weight = 1; Profit / Weight = 8 / 1 = 8
Profit = 9; Weight = 3; Profit / Weight = 9 / 3 = 3
Profit = 4; Weight = 2; Profit / Weight = 4 / 2 = 2
Now, we will select the items according to the maximum Profit
divided by Weight ratio.
Objects Profit [P] Weight [W] Remaining
Weight
5 8 1 15 – 1 = 14
1 5 1 14 – 1 = 13
2 10 3 13 – 3 = 10
3 15 5 10 – 5 = 5
6 9 3 5–3=2
7 4 2 2–2=0
Total Profit = 51
Max. Profit = 8; Object = 5; Profit = 8; Weight = 1;Remaining Weight
= 15 – 1 = 14
Max. Profit = 5; Object = 1; Profit = 5;Weight = 1; Remaining Weight
= 14 – 1 = 13
Max. Profit = 3.3; Object = 2; Profit = 10;Weight = 3; Remaining
Weight = 13 – 3 = 10
Max. Profit = 3; Object = 3; Profit = 15;Weight = 5; Remaining
Weight = 10 – 5 = 5
Max. Profit = 3; Object = 6; Profit = 9;Weight = 3; Remaining Weight
=5–3=2
Max. Profit = 2; Object = 7; Profit = 4;Weight = 2; Remaining Weight
=2–2=0
So, the Total Max. Profit = 51 and we have got this Max. Profit in 3 rd
approach. So, Profit divided by Weight ratio is the best one.
In, fractional Knapsack problem you will find out the Optimal result
when you apply Greedy Method.
But in 0 / 1 Knapsack problem it is better to use Dynamic
Programming.
Optimal Storage on Tapes
There are n programs that are to be stored on a computer tape. So, let
us assume that we have n programs and we need to store all those
programs on a computer tape. Let the length of each program is
denoted by li .
So, length of the first program will become l1. Length of second
program will become l2 and so on.
Tape is nothing but Magnetic Tape. Magnetic Tape provides
sequential access that means we can retrieve the programs, we can
access the programs one – by – one. We can access the first program
directly, but, if you want to access the second program, before the
second program we must access first program. If you want to retrieve
fifth program then we must retrieve all the programs before the fifth
program, so, before fifth program we must retrieve first program,
second program, third program, fourth program and then fifth
program. After retrieving each record the corresponding pointer will
be placed at the first position only, so, if you want to access the last
program then before that we need to access all the programs from first
program to last but one program, that is the property of the tape or
magnetic tape.
Our main aim is we have to store all the programs on a Computer tape
with minimum retrieval time.
Example :
Consider n = 3, that means the number of programs are 3 and lengths
are (l1, l2, l3) = (5, 10, 3). Find the Optimal Storage order. That
means in which order if you store the program then the retrieval time
is minimum. Number of tapes is 1.
Sol :
For these 3 programs the possible solutions or the orderings are n!.
In this case it is going to be 3! that is 6 orderings . The following are
the ordering in tabular format.
Ordering Number Program Order
1 1 2 3
2 1 3 2
3 2 1 3
4 2 3 1
5 3 1 2
6 3 2 1
Program order 1 2 3 means first program will be accessed first
followed by second program followed by third program. In the similar
manner the remaining programs will be accessed.
Now, we will see how much time is required for each ordering.
Ordering Program Order d(I)
Number
1 1 2 3 5 + (5 + 10) (5 + 10 + 3) = 38
2 1 3 2 5 + (5 + 3) (5 + 3 + 10) = 31
3 2 1 3 10 + (10 + 5) + (10 + 5 + 3) = 43
4 2 3 1 10 + (10 + 3) + (10 + 3 + 5) = 41
5 3 1 2 3 + (3 + 5) (3 + 5 + 10) = 29
6 3 2 1 3 + (3 + 10) (3 + 10 + 5) = 34
Consider if the programs are stored in the order of 1 2 3 the time
required to read the first program will be the length of the first
program which is 5, the time required to retrieve the second program
is, length of the first program and length of the second program which
is (5 + 10). The time required to retrieve the third program is 1 + 2 + 3
or (5 + 10 + 3).
(1 + 2 + 3) is nothing but length of the first program, length of the
second program and length of the third program. So, total time
required is 38.
If we will go for the order 2 3 1, the time required for second program
is 10, so, time required for this third program will be (10 + 3) and the
time required for the first program will be (10 + 3 + 5). So, total time
is 41.
In this manner we have calculated the times for every combination.
Now, we have to calculate the minimum time taken to retrieve the
programs is as follows.
Ordering Program d(I) Mean Retrieval
Number Order Time[MRT]
1 1 2 3 5 + (5 + 10) (5 + 10 + 38 / 3 = 12.66
3) = 38
2 1 3 2 5 + (5 + 3) (5 + 3 31 / 3 = 10.33
+ 10) = 31
3 2 1 3 10 + (10 + 5) + (10 + 43 / 3 = 14.33
5 + 3) = 43
4 2 3 1 10 + (10 + 3) + (10 + 41 / 3 = 13.33
3 + 5) = 41
5 3 1 2 3 + (3 + 5) (3 + 5 + 29 / 3 = 9.66
10) = 29
6 3 2 1 3 + (3 + 10) (3 + 10 + 34 / 3 = 11.33
5) = 34
As we have calculated the Mean Retrieval Time [MRT], now, we
have to find the Optimal solution which is 9.66.
If we will store the program in the ordering of 3 1 2 we are getting
this d(I) = 29 and MRT = 9.66.
Approach to Obtain Optimal Solution
Find all the permutations of the programs and find Optimal solution
[Minimum MRT].
Drawback
For the large value of n, time will be high to find all possible
permutations.
What can be the other approach which will save you time? Greedy
approach to obtain the solution.
Greedy Approach to obtain Optimal Solution
If you have observed which Optimal which ordering you have given
the Optimal solution. It is nothing but, store the programs in
increasing order of their lengths using any sorted order.
Time required for sorting is nlogn.
That is in the above example increasing order of the lengths are 3, 5,
10 and then we have seen that this ordering 3 1 2 and the time
required is always less.
The approach is that arrange at an increasing order of the length and
then find out its Mean Retrieval Time[MRT].
Example 2
Let n = 10, that means totally there are 10 programs and lengths are
(L1, L2, L3, L4, L5, L6, L7, L8, L9, L10) = (10, 20, 45, 70, 1, 3, 7,
54, 23, 67)
L1 means length of the first program, L2 means length of the second
program, likewise L10 means length of the tenth program.
Here, first we have to arrange all the elements in ascending order of
length of the program.
Ascending Order : 1, 3, 7, 10, 20, 23, 45, 54, 67, 70
Let us assume that we have 3 tapes i.e.,
Tape 0 : First Tape
Tape 1: Second Tape
Tape 2 : Third Tape
The first three elements are 1, 3, 7. Here, we are assigning 1 to Tape
0, 3 to Tape 1 and 7 to Tape 2.
Depending upon the number of tapes we have to store the lengths in
the tapes.
Next, 10 is stored on Tape 0; 20 is assigned to Tape 1, 23 is assigned
to Tape 2. Next, 45, is stored in Tape 0, 54 is stored in Tape 1, 67 is
stored in Tape 2, next , 70 is stored in Tape 0.
The following are the storage of lengths of the programs on Tapes.
Tape 0 1 10 45 70 1 + (1 + 10) + (1 + 10 + 45) + (1 + 10 + 45 + 70) =
194
Tape 1 3 20 54 3 + (3 + 20) + (3 + 20 + 54) = 103
Tape 2 7 23 67 7 + (7 + 23) + (7 + 23 + 67) = 134
We can access this 1 directly, that is we can retrieve the first record
length directly. We can access the second program only after
accessing the first program. That is 1 + (1 +10). Next, we can retrieve
the third program only after retrieving the first two programs. That is
1 + (1 + 10) + (1 + 10 + 45). Next, we can retrieve the last program,
only after retrieving the first three programs.
That is, 1 + (1 + 10) + (1 + 10 + 45) + (1 + 10 + 45 + 70) = 194.
Total retrieval time is calculated by adding the Retrieval time of Tape
0, Retrieval time of Tape 1, Retrieval time of Tape 2.
Total Retrieval Time = 194 + 103 + 134 = 431
Means Retrieval Time, means Average Retrieval Time is 431 / 3 =
143.67
