Instructor
Neelima Gupta
ngupta@cs.du.ac.in
Instructor: Ms. Neelima Gupta
Interval/Job Scheduling –a
greedy approach
Weighted Interval Scheduling –
•Each jobi has (si , fi , pi)
starting time si ,
finishing time fi, and
profit pi
• Aim: Find an optimal schedule of job that makes
the maximum profit.
• Greedy approach : choose the job which finishes
first…..does not work.
Thanks to Neha (16)
i Si Fi Pi
2 2 4 3
1 1 5 10
3 4 6 4
4 5 8 20
5 6 9 2
Thanks to Neha (16)
Weighted Interval Scheduling
P(1)=10
P(2)=3
P(3)=4
P(4)=20
P(5)=2
0 1 2 3 4 5 6 7 8 9 Time
Thanks to Neha (16)
Greedy Approach
P(1)=10
P(2)=3
P(4)=20
P(5)=2
0 1 2 3 4 5 6 7 8 9 Time
Thanks to Neha (16)
Greedy does not work
P(1)=10
P(2)=3
Optimal
schedule
P(4)=20
Schedule
chosen by
P(5)=2 greedy app
0 1 2 3 4 5 6 7 8 9 Time
Greedy approach takes job 2, 3 and 5 as best schedule and makes profit of
7. While optimal schedule is job 1 and job4 making profit of 30 (10+20).
Hence greedy will not work
Thanks to Neha (16)
DP Solution for WIS
Let m[j]= optimal schedule solution from the first jth
jobs, (jobs are sorted in the increasing order of their
finishing times)
pj=profit of jth job.
p[j] =largest index i<j , such that interval i and j
are disjoint i.e. i is the rightmost interval that ends
before j begins or
the last interval compatible with j and is
before j.
Thanks to :
Neha Mishra (roll no:18)
DP Solution for WIS
Either j is in the optimal solution or it is not.
If it is, then m[j] = pj + profit when considering the jobs
before and including the last job compatible with j
i.e. m[j] = pj + m[p(j)]
If it is not, then m[j] = m[j-1]
Thus,
m[j]= max(pj + m[p(j)], m[j-1])
Recursive Paradigm
Write a recursive function to compute m[n]…afterall
we are only interested in that.
some of the problems are solved several times leading
to exponential time.
INDE
X V1=2 P[1]=0
1 V2=4
2 V3=4
3
V4=7
4
V5=2
5
V6=1
6
Thanks to : Nikita Khanna(19)
INDE
X V1=2 P[1]=0
1 V2=4 P[2]=0
2 V3=4
3
V4=7
4
V5=2
5
V6=1
6
Thanks to : Nikita Khanna(19)
INDE
X V1=2 P[1]=0
1 V2=4 P[2]=0
2 V3=4 P[3]=1
3
V4=7
4
V5=2
5
V6=1
6
Thanks to : Nikita Khanna(19)
Thanks to : Nikita Khanna(19)
INDE
X V1=2 P[1]=0
1 V2=4 P[2]=0
2 V3=4 P[3]=1
3 P[4]=
V4=7
0
4
V5=2
5
V6=1
6
Thanks to : Nikita Khanna(19)
Thanks to : Nikita Khanna(19)
INDE
X V1=2 P[1]=0
1 V2=4 P[2]=0
2 V3=4 P[3]=1
3 P[4]=
V4=7
0
4
V5=2 P[5]=3
5
V6=1
6
Thanks to : Nikita Khanna(19)
Thanks to : Nikita Khanna(19)
INDE
X V1=2 P[1]=0
1 V2=4 P[2]=0
2 V3=4 P[3]=1
3 P[4]=
V4=7
0
4
V5=2 P[5]=3
5
V6=1
P[6]=3
6
Thanks to : Nikita Khanna(19)
Thanks to : Nikita Khanna(19)
Recursive Paradigm : tree of
recursion for WIS
Recursive Paradigm
Sometimes some of the problems are solved several
times leading to exponential time. For example:
Fibonacci numbers.
DP Solution: Solve a problem only once and use it as
and when required
Top-down DP …..Memoization….generally storage cost is
large
Bottom-Up DP …….Iterative
Principles of DP
m[j] = max{m[j-1], m[p[j] ] + pj}
m 0 1 2 3 4
5 6
Thanks to : Nikita Khanna(19)
m[j] = max{m[j-1], m[p[j] ] + pj}
0
m 0 1 2 3 4
5 6
Thanks to : Nikita Khanna(19)
m[j] = max{m[j-1], m[p[j] ] + pj}
Max{0,0+2}
0 2
m 0 1 2 3 4
5 6
Thanks to : Nikita Khanna(19)
m[j] = max{m[j-1], m[p[j] ] + pj}
Max{0,0+2}
Max{2,0+4
}
0 2 4
m 0 1 2 3 4
5 6
Thanks to : Nikita Khanna(19)
m[j] = max{m[j-1], m[p[j] ] + pj}
Max{0,0+2}
Max{2,0+4
}
0 2 4 6
m 0 1 2 3 4
5 6
Max{4,2+4}
Thanks to : Nikita
) Khanna(19)
m[j] = max{m[j-1], m[p[j] ] + pj}
Max{0,0+2}
Max{2,0+4 Max{6,0+7}
}
0 2 4 6 7
m 0 1 2 3 4
5 6
Max{4,2+4}
Thanks to : Nikita Khanna(19)
m[j] = max{m[j-1], m[p[j] ] + pj}
Max{0,0+2}
Max{2,0+4 Max{6,0+7}
}
0 2 4 6 7 8
m 0 1 2 3 4
5 6
Max{7,6+2}
Max{4,2+4}
Thanks to : Nikita Khanna(19)
Thanks to : Nikita Khanna(19)
m[j] = max{m[j-1], m[p[j] ] + pj}
Max{0,0+2} Max{8,6+1}
Max{6,0+7}
Max{2,0+4
}
0 2 4 6 7 8 8
m 0 1 2 3 4
5 6
Max{7,6+2}
Max{4,2+4}
Thanks to : Nikita Khanna(19)
Thanks to : Nikita Khanna(19)
FRACTIONAL KNAPSACK PROBLEM
Given a set S of n items, with value vi and weight wi and a
knapsack with capacity W.
Aim: Pick items with maximum total value but with weight
at most W. You may choose fractions of items.
GREEDY APPROACH
Pick the items in the decreasing order of value per unit
weight i.e. highest first.
Example
knapsack capacity 50
Item 2 item 3
Item 1
30
20
10
● vi = 60 vi = 100 vi = 120
vi/ wi =6 vi/ wi =5 vi/ wi =4
Thanks to:
Neha Katyal
Example
knapsack capacity 50
Item 2 item 3
30
● 20
●
10 60
vi = 100 vi = 120
vi/ wi = 5 vi/ wi = 4
Thanks to:
Neha
Katyal
Example
knapsack capacity 50
item 3
20
100
30
● +
●
10 60
vi = 120
vi/ wi = 4
Thanks to:
Neha Katyal
Example
knapsack capacity 50
$80
20/
30
+
20 100
10 60
= 240
Thanks to:
Neha Katyal
0-1 Kanpsack
example to show that the above greedy approach will not
work,
So, DP
GREEDY APPROACH DOESN’T WORK
FOR 0-1 KNAPSACK
Counter Example:
knapsack
Item 2 item 3
Item 1
20 30
10
● vi = $60 vi = $100 vi = $120
vi/ wi =6 vi/ wi =5 vi/ wi =4
Thanks to:
Neha Katyal
Example
knapsack
Item 2 item 3
30
● 20
●
10 $60
vi = $100 vi = $120
vi/ wi = 5 vi/ wi = 4
Thanks to:
Neha Katyal
Example
knapsack
item 3
20
$100
30
● +
●
10 $60
vi = $120 = $160
vi/ wi = 4
suboptimal
Thanks to:
Neha Katyal
Fractional Knapsack –a greedy
approach
DP Solution for 0-1KS
Let m[I,w] be the optimal value obtained when
considering objects upto I and filling a knapsack of
capacity w
m[0,w] = 0
m[i,0] = 0
m[i,w] = m[i-1,w] if wi > w
m[i,w] = max{m[i-1, w-wi] + vi , m[i-1, w]} if wi <= w
Example
n=4
W=5
Elements (weight, value):
(2,3), (3,4), (4,5), (5,6)
Thanks to : Neha Katyal (17, MCS '11), Shikha
Walia (27, MCS'11)
(2,3), (3,4), (4,5), (5,6)
W 0 1 2 3 4 5
i
0 0 0 0 0 0
0
0
1
0
2
0
3
0
4
Thanks to : Neha Katyal (17, MCS '11), Shikha
Walia (27, MCS'11)
(2,3), (3,4), (4,5), (5,6)
As w<w1 ; m[1,1] = m[1-1,1] = m[0,1]
W 0 1 2 3 4 5
i
0 0 0 0 0 0
0
0 0
1
0
2
0
3
0
4
Thanks to : Neha Katyal (17, MCS '11), Shikha
Walia (27, MCS'11)
(2,3), (3,4), (4,5), (5,6)
As w<w2 ; m[2,1] = m[2-1,1] = m[1,1]
W 0 1 2 3 4 5
i
0 0 0 0 0 0
0
0 0
1
0 0
2
0
3
0
4
Thanks to : Neha Katyal (17, MCS '11), Shikha
Walia (27, MCS'11)
(2,3), (3,4), (4,5), (5,6)
As w<w3 ; m[3,1] = m[3-1,1] = m[2,1]
W 0 1 2 3 4 5
i
0 0 0 0 0 0
0
0 0
1
0 0
2
0 0
3
0
4
Thanks to : Neha Katyal (17, MCS '11), Shikha
Walia (27, MCS'11)
(2,3), (3,4), (4,5), (5,6)
As w<w4 ; m[4,1] = m[4-1,1] = m[3,1]
W 0 1 2 3 4 5
i
0 0 0 0 0 0
0
0 0
1
0 0
2
0 0
3
0 0
4
Thanks to : Neha Katyal (17, MCS '11), Shikha
Walia (27, MCS'11)
(2,3), (3,4), (4,5), (5,6)
As w>=w1 ; m[1,2] = max{m[1-1,2] , m[1-1,2-2]+3}
=max{ 0,0+3}
W 0 1 2 3 4 5
i
0 0 0 0 0 0
0
0 0 3
1
0 0
2
0 0
3
0 0
4
Thanks to : Neha Katyal (17, MCS '11), Shikha
Walia (27, MCS'11)
(2,3), (3,4), (4,5), (5,6)
As w<w2 ; m[2,2] = m[2-1,2] = m[1,2]
W 0 1 2 3 4 5
i
0 0 0 0 0 0
0
0 0 3
1
0 0 3
2
0 0
3
0 0
4
Thanks to : Neha Katyal (17, MCS '11), Shikha
Walia (27, MCS'11)
(2,3), (3,4), (4,5), (5,6)
As w<w3 ; m[3,2] = m[3-1,2] = m[2,2]
W 0 1 2 3 4 5
i
0 0 0 0 0 0
0
0 0 3
1
0 0 3
2
0 0 3
3
0 0
4
Thanks to : Neha Katyal (17, MCS '11), Shikha
Walia (27, MCS'11)
(2,3), (3,4), (4,5), (5,6)
As w<w4 ; m[4,2] = m[4-1,2] = m[3,2]
W 0 1 2 3 4 5
i
0 0 0 0 0 0
0
0 0 3
1
0 0 3
2
0 0 3
3
0 0 3
4
Thanks to : Neha Katyal (17, MCS '11), Shikha
Walia (27, MCS'11)
(2,3), (3,4), (4,5), (5,6)
As w>=w1 ; m[1,3] = max{m[1-1,3] , m[1-1,3-2]+3}
=max{ 0,0+3}
W 0 1 2 3 4 5
i
0 0 0 0 0 0
0
0 0 3 3
1
0 0 3
2
0 0 3
3
0 0 3
4
Thanks to : Neha Katyal (17, MCS '11), Shikha
Walia (27, MCS'11)
(2,3), (3,4), (4,5), (5,6)
As w>=w2 ; m[2,3] = max{m[2-1,3] , m[2-1,3-3]+4}
=max{ 3,0+4}
W 0 1 2 3 4 5
i
0 0 0 0 0 0
0
0 0 3 3
1
0 0 3 4
2
0 0 3
3
0 0 3
4
Thanks to : Neha Katyal (17, MCS '11), Shikha
Walia (27, MCS'11)
(2,3), (3,4), (4,5), (5,6)
As w<w3 ; m[3,3] = m[3-1,3] = m[2,3]
W 0 1 2 3 4 5
i
0 0 0 0 0 0
0
0 0 3 3
1
0 0 3 4
2
0 0 3 4
3
0 0 3
4
Thanks to : Neha Katyal (17, MCS '11), Shikha
Walia (27, MCS'11)
(2,3), (3,4), (4,5), (5,6)
As w<w4 ; m[4,3] = m[4-1,3] = m[3,3]
W 0 1 2 3 4 5
i
0 0 0 0 0 0
0
0 0 3 3
1
0 0 3 4
2
0 0 3 4
3
0 0 3 4
4
Thanks to : Neha Katyal (17, MCS '11), Shikha
Walia (27, MCS'11)
(2,3), (3,4), (4,5), (5,6)
As w>=w1 ; m[1,4] = max{m[1-1,4] , m[1-1,4-2]+3}
=max{ 0,0+3}
W 0 1 2 3 4 5
i
0 0 0 0 0 0
0
0 0 3 3 3
1
0 0 3 4
2
0 0 3 4
3
0 0 3 4
4
Thanks to : Neha Katyal (17, MCS '11), Shikha
Walia (27, MCS'11)
(2,3), (3,4), (4,5), (5,6)
As w>=w2 ; m[2,4] = max{m[2-1,4] , m[2-1,4-3]+4}
=max{ 3,0+4}
W 0 1 2 3 4 5
i
0 0 0 0 0 0
0
0 0 3 3 3
1
0 0 3 4 4
2
0 0 3 4
3
0 0 3 4
4
Thanks to : Neha Katyal (17, MCS '11), Shikha
Walia (27, MCS'11)
(2,3), (3,4), (4,5), (5,6)
As w>=w3 ; m[3,4] = max{m[3-1,4] , m[3-1,4-4]+5}
=max{ 4,0+5}
W 0 1 2 3 4 5
i
0 0 0 0 0 0
0
0 0 3 3 3
1
0 0 3 4 4
2
0 0 3 4 5
3
0 0 3 4
4
Thanks to : Neha Katyal (17, MCS '11), Shikha
Walia (27, MCS'11)
(2,3), (3,4), (4,5), (5,6)
As w<w4 ; m[4,4] = m[4-1,4] = m[3,4]
W 0 1 2 3 4 5
i
0 0 0 0 0 0
0
0 0 3 3 3
1
0 0 3 4 4
2
0 0 3 4 5
3
0 0 3 4 5
4
Thanks to : Neha Katyal (17, MCS '11), Shikha
Walia (27, MCS'11)
(2,3), (3,4), (4,5), (5,6)
As w>=w1 ; m[1,5] = max{m[1-1,5] , m[1-1,5-2]+3}
=max{ 0,0+3}
W 0 1 2 3 4 5
i
0 0 0 0 0 0
0
0 0 3 3 3 3
1
0 0 3 4 4
2
0 0 3 4 5
3
0 0 3 4 5
4
Thanks to : Neha Katyal (17, MCS '11), Shikha
Walia (27, MCS'11)
(2,3), (3,4), (4,5), (5,6)
As w>=w2 ; m[2,5] = max{m[2-1,5] , m[2-1,5-3]+4}
=max{ 3,3+4}
W 0 1 2 3 4 5
i
0 0 0 0 0 0
0
0 0 3 3 3 3
1
0 0 3 4 4 7
2
0 0 3 4 5
3
0 0 3 4 5
4
Thanks to : Neha Katyal (17, MCS '11), Shikha
Walia (27, MCS'11)
(2,3), (3,4), (4,5), (5,6)
As w>=w3 ; m[3,5] = max{m[3-1,5] , m[3-1,5-4]+5}
=max{ 7,0+5}
W 0 1 2 3 4 5
i
0 0 0 0 0 0
0
0 0 3 3 3 3
1
0 0 3 4 4 7
2
0 0 3 4 5 7
3
0 0 3 4 5
4
Thanks to : Neha Katyal (17, MCS '11), Shikha
Walia (27, MCS'11)
(2,3), (3,4), (4,5), (5,6)
As w>=w4 ; m[4,5] = max{m[4-1,5] , m[4-1,5-5]+6}
=max{ 7,0+6}
W 0 1 2 3 4 5
i
0 0 0 0 0 0
0
0 0 3 3 3 3
1
0 0 3 4 4 7
2
0 0 3 4 5 7
3
0 0 3 4 5 7
4
Thanks to : Neha Katyal (17, MCS '11), Shikha
Walia (27, MCS'11)
(2,3), (3,4), (4,5), (5,6)
W 0 1 2 3 4 5
i
0 0 0 0 0 0
0
0 0 3 3 3 3
1
0 0 3 4 4 7
2
0 0 3 4 5 7
3
0 0 3 4 5 7
4
Thanks to : Neha Katyal (17, MCS '11), Shikha
Walia (27, MCS'11)
Pseudo-polynomial algorithm
An algorithm that is polynomial in the numeric value
of the input (which is actually exponential in the size
of the input – the number of digits).
Thus O(n) time algorithm to test whether n is prime or
not is pseudo-polynomial.
DP solution to 0-1 Knapsack is pseudo-polynomial as it
is polynomial in K, the capacity (one of the inputs) of
the Knapsack.
Weakly/Strongly NPC problems
An NP complete problem with a known pseudo-
polynomial solution is stb weakly NPC.
An NPC problem for which it has been proved that it
cannot admit a pseudo-polynomial solution unless P=
NP is stb strongly NPC.
