Question

Greedy algorithms.

1. For fractional Snapsack problem, the thief can carry at most 20 pounds. If the thief finds the following items: (22 dollars, 7 pounds), (20, dollar, 5 pounds), (50 dollars, 100 pounds), (3 dollar, 1 pounds), (20 dollars, 10 pounds) , and (5 dollars, 0.5 pounds), what should the thief choose?
2. For the interval scheduling problem, the set of jobs (si, fi) are as follows: (3, 6), (2, 4), (5, 9) (7, 10), (0, 9), (1, 3), (9, 11), and (6, 7). Use the greedy algorithm to give the maximum number of compatible jobs.

Answer 1

Fractional Knapsack

n = 6

w = 20 pounds

Item	Weight	Value	Value/Weight
1	7	22	3.14
2	5	20	4
3	100	50	0.5
4	1	3	3
5	10	20	2
6	0.5	5	10

Sort all the items in decreasing order of their value / weight ratio

I6	I2	I1	I4	I5	I3
10	4	3.14	3	2	0.5

Construct a table with Remaining knapsack weight, Items in kanpsack and total profit obtained

Knapsack Weight	Items in Knapsack	Profit
20	Ø	0
19.5	I6	5
14.5	I6,I2	25
7.5	I6,I2,I1	47
6.5	I6,I2,I1,I4	50
0	I6,I2,I1,I4,I5(6.5)	50+(6.5*2)

Maximum profit that can be gained is 63 by placing I6,I2,I1,I4 and 6.5 pounds of I5 in the knapsack.

Interval Scheduling

Set of jobs (si, fi) are as follows: (3, 6), (2, 4), (5, 9) (7, 10), (0, 9), (1, 3), (9, 11), and (6, 7)

Job	Start Time	Finish Time
J1	3	6
J2	2	4
J3	5	9
J4	7	10
J5	0	9
J6	1	3
J7	9	11
J8	6	7

Sort in the descending order of finish time

Job	Start Time	Finish Time
J6	1	3
J2	2	4
J1	3	6
J8	6	7
J3	5	9
J5	0	9
J4	7	10
J7	9	11

For each job, check if it is overlapping with the previous job i.e., starttime of current job is less than finish time of previous job

Job	Start Time	Finish Time
J6	1	3

Next, (1,3) and (2,4) are overlapping as 2<3

Job	Start Time	Finish Time
J6	1	3
J1	3	6

Job	Start Time	Finish Time
J6	1	3
J1	3	6
J8	6	7

Next, (6,7) and (5,9) are overlapping as 5<7

Next, (6,7) and (0,9) are overlapping as 0<7

Job	Start Time	Finish Time
J6	1	3
J1	3	6
J8	6	7
J4	7	10

Next, (7,10) and (9,11) are overlapping as 9<10

Hence, the intervals to be considered are (1,3)(3,6)(6,7)(7,10)

Hope it helps! If there are any doubts or discrepancies do comment below! We are available!:) Give your valuable upvote if you are satisfied with the answer!:))))