Department of IT Engineering

Chapter 5
Greedy Algorithms

Subject Code: 01CE0503

Design and Analysis of Algorithm (DAA)

Prof. Yatri Davda

 Outline
Looping
 General Characteristics of greedy algorithms
 Elements of Greedy Strategy
 The Fractional Knapsack Problem
 Activity selection problem
 Job Scheduling Problem
Introduction
Characteristics of Greedy Algorithms

Greedy algorithms are characterized by the following features.
1. Greedy approach forms a set or list of candidates 𝑪.
2. Once a candidate is selected in the solution, it is there forever: once a candidate is excluded
from the solution, it is never reconsidered.
3. To construct the solution in an optimal way, Greedy Algorithm maintains two sets.
4. One set contains candidates that have already been considered and chosen, while the other
set contains candidates that have been considered but rejected.


The greedy algorithm consists of four functions.
i. Solution Function:- A function that checks whether chosen set of items provides a solution.
ii. Feasible Function:- A function that checks the feasibility of a set.
iii. Selection Function:- The selection function tells which of the candidates is the most
promising.
iv. Objective Function:- An objective function, which does not appear explicitly, but gives the
value of a solution.
Knapsack Problem
Knapsack Problem
Fractional Knapsack Problem
Introduction

We are given objects and a knapsack.

Object has a positive weight and a positive value for

The knapsack can carry a weight not exceeding .

Our aim is to fill the knapsack in a way that maximizes the value of the included
objects, while respecting the capacity constraint.

In a fractional knapsack problem, we assume that the objects can be broken into
smaller pieces.

So we may decide to carry only a fraction of object , where

In this case, object contribute to the total weight in the knapsack, and to the value of
the load.

Symbolic Representation of the problem can be given as follows:
maximize subject to
Where, and for .
Fractional Knapsack Problem - Example

We are given objects and the weight carrying capacity of
knapsack is .

For each object, weight and value are given in the following table.

Object


Fill the knapsack with given objects such that the total value of
knapsack is maximized.
Fractional Knapsack Problem - Greedy Solution

Three Selection Functions can be defined as,
1. Sort the items in descending order of their values and
select the items till weight criteria is satisfied.
2. Sort the items in ascending order of their weight and
select the items till weight criteria is satisfied.
3. To calculate the ratio value/weight for each item and sort
the item on basis of this ratio. Then take the item with the
highest ratio and add it.
Fractional Knapsack Problem - Greedy Solution
Object

2.0 1.5 2.2 1.0 1.2

Selectio Objects Value Weight

n 1 2 3 4 5 Capacity
100
30 50 20
0 0 1 0.5 1 146
10 20 30 40
1 1 1 1 0 156
30 10 20 40
1 1 1 0 0.8 164
Profit
Profit===66
Profit 66+++60
20 20+++(40
30 30 *++0.5)
66 48 ===
40
164
146
156
Fractional Knapsack Problem - Algorithm
Algorithm: Greedy-Fractional-Knapsack (w[1..n], p[1..n], W)
for i = 1 to n do
x[i] 0 ; weight 0
While weight < W do
i the best remaining object
if weight + w[i] ≤ W then W = 100 and Current weight in
knapsack= 60
x[i] 1 Object weight = 50
The fraction of object to be included will
weight weight + w[i] be
else (100 – 60) / 50 = 0.8

x[i] (W - weight) / w[i]

weight W
return x
 Exercises – Home Work
1. Consider Knapsack capacity , and find the maximum
profit using greedy approach.
2. Consider Knapsack capacity , and . Find the maximum
profit using greedy approach.
Activity Selection Problem
Introduction

The Activity Selection Problem is an optimization problem
which deals with the selection of non-overlapping activities
that needs to be executed by a single person or a machine in
a given time duration.

An activity-selection can also be applicable for scheduling a
resource among several competing activities.

We are given a set of activities with start time and finish
time , of an activity. Find the maximum size set of mutually
compatible activities.

Activities andare compatible if the half-open internal and do
not overlap, that is, and are compatible if or .
Activity Selection Problem - Example
Sr Activity (, ) Example: 11 activities are given as,
.
1 P (1, 4) Solution:
2 Q (3, 5)
3 R (0, 6) Step 1:
Sort the activities of set 𝑺 as per
4 S (5, 7)
increasing finish time to directly identify
5 T (3, 8)
mutually compatible activities by
6 U (5, 9) comparing finish time of first activity and
7 V (6, 10) start time of next activity
8 W (8, 11)
9 X (8, 12)
10 Y (2, 13)
11 Z (12, 14)
Activity Selection Problem - Example
Sr Activity (, ) Example: 11 activities are given as,
.
1 P (1, 4) Solution:
2 Q (3, 5)
3 R (0, 6) Step 2:
1. A = {P}
4 S (5, 7)
2. A = {P, S}
5 T (3, 8)
3. A = {P, S, W}
6 U (5, 9) 4. A = {P, S, W, Z}
7 V (6, 10)
8 W (8, 11) Answer: A = {P, S, W, Z}
9 X (8, 12)
10 Y (2, 13)
11 Z (12, 14)
Activity Selection - Algorithm
Algorithm: Activity Selection
Step I: Sort the input activities by increasing
finishing time. f1 ≤  f2 ≤  . . . ≤  fn

Step II: Call GREEDY-ACTIVITY-SELECTOR (s, f)

n = length [s]
A = {i}
j = 1
for  i = 2  to  n

        do if   si ≥ fj

             then  A = A U {i}
                      j = i
return  set A
Exercise - HW

Given arrival and departure times of all trains that
reach a railway station, find the minimum number of
platforms required for the railway station so that no
train waits. We are given two arrays which represent
arrival and departure times of trains that stop. Arr[ ]
= {9:00, 9:40, 9:50, 11:00, 15:00, 18:00} dep[ ] =
{9:10, 12:00, 11:20, 11:30, 19:00, 20:00}
Job Scheduling with Deadlines
Introduction

We have set of jobs to execute, each of which takes unit
time.

At any point of time we can execute only one job.

Jobearns profit if and only if it is executed no later than its
deadline

We have to find an optimal sequence of jobs such that our
total profit is maximized.

Feasible jobs: A set of job is feasible if there exits at least
one sequence that allows all the jobs in the set to be
executed no later than their respective deadlines.
Job Scheduling with Deadlines - Example

Using greedy algorithm find an optimal schedule for following jobs with .

Profits: &

Deadline:

Solution:
Step Sort
1: the jobs in decreasing order of their profit.

Job
Profit
Deadline
Job Scheduling with Deadlines - Example
Job
Profit
Deadline

Step 2: Find total position

Here,
P 1 2 3
Job selected 0 0 0

Step 3: : assign job to position

P 1 2 3
Job selected 0 0 J1
Job Scheduling with Deadlines - Example
Job
Profit
Deadline

Step 4: assign job to position

P 1 2 3
Job selected J2 0 J1

Step 5: : assign job to position

But position 1 is already occupied and two

jobs can not be executed in parallel, so
reject job 3
Job Scheduling with Deadlines - Example
Job
Profit
Deadline
Step 6:
assign job to position as, position is not free but position is free.

P 1 2 3
Job selected J2 J4 J1

Now no more free position is left so no more jobs can be scheduled.

The final optimal sequence:

Execute the job in order 2, 4, 1 with total profit value 42.

 Exercises – Home Work
1. Using greedy algorithm find an optimal schedule for
following jobs with 𝒏=4.
Profits: (a, b, c, d) = (20,10,40,30) &
Deadline: (d1, d2, d3, d4) = (4, 1, 1, 1)

2. Using greedy algorithm find an optimal schedule for

following jobs with 𝒏=5.
Profits: (a, b, c, d, e) = (100,19,27,25,15) &
Deadline: (d1, d2, d3, d4, d5) = (2, 1, 2, 1, 3)
 Job Scheduling with Deadlines - Algorithm
Algorithm: Job-Scheduling (P[1..n], D[1..n])
1. Sort all the n jobs in decreasing order of their profit.

2. Let total position P = min(n, max(d i))

3. Each position 0, 1, 2…, P is in different set and T({i}) = i, for 0 ≤ i ≤
P.
4. Find the set that contains d, let this set be K. if T(K) = 0 reject the
job; otherwise:
1.Assign the new job to position T(K).
2.Find the set that contains T(K) – 1. Call this
set L.
3.Merge K and L. the value for this new set is the
old value of T(L).
Thank You!