Design & Analysis of Algorithm

(DAA)
Dynamic programming & its applications
Dept. of CSE, rcciit

1
 Table of Content Module 2
▪ Dynamic Programming
▪ Definition, characteristics & Applications
▪ Dynamic Programming – difference with D & C
▪ Matrix-Chain Multiplication,
▪ All Pair Shortest Paths - Floyd-Warshall algorithm
▪ Single Source Shortest Path - Bellman-Ford algorithm
▪ Travelling Salesman Problem,
▪ 0-1 Knapsack Problem
 Dynamic programming (DP) ….?????
• Dynamic Programming is the most powerful design technique for solving
optimization problems.
• Dynamic programming (DP) is closely related to divide and conquer technique,
where the problem breaks down into smaller disjoin sub problems and each
sub problem is solved recursively and then combine their solution to solve the
original problems.
• Dynamic Programming is used when the subproblems are not
independent, e.g. when they share the same subproblems. In this case,
divide and conquer may do more work than necessary, because it solves
the same sub problem multiple times.
• Dynamic Programming solves each subproblems just once and stores
the result in a table so that it can be repeatedly retrieved if needed
again.
• Dynamic programming (DP) is a bottom up technique, which is used to solve
all possible small problems and then combine them to obtain solutions for
bigger problems.
• Dynamic programming (DP) is the most powerful technique for optimization
problems was invented by Richard Bellman in the 1950s.
• Dynamic programming (DP) is to avoid the requirement of calculating the same
quantity twice.
 Steps for achieving Dynamic Programming
The steps for achieving Dynamic Programming are :
• Divide (Sub problems) - The main problem is divided into
several smaller subproblems. The solution of the main problem
is expressed in terms of the solution for the smaller
subproblems.

• Table (Storage) - The solution for each subproblem is stored in a

table. So that it can be used many times whenever required.

• Combine (Bottom-up Computation) - The solution to main

problem is obtained by combining the solutions of smaller
subproblems.
 Characteristics of Dynamic programming
Dynamic programming is a technique for solving problems with a recursive
structure with the following characteristics:

1. Optimal Substructure (principle of optimality): An optimal solution to a

problem can be decomposed into optimal solutions for sub-problems

2. Overlapping Sub-problems: During the computation same instances are

referred to over and over again . When a recursive algorithm would visit
the same subproblems repeatedly, then a problem has overlapping
subproblems.

•If a problem has optimal substructure, then we can recursively define an optimal
solution. If a problem has overlapping subproblems, then we can improve on a
recursive implementation by computing each subproblem only once.
•If the space of subproblems is enough (i.e. polynomial in the size of the input),
dynamic programming can be much more efficient than recursion.
 Elements of Dynamic Programming
There are basically three elements that characterize a dynamic programming
algorithm:-
[Link]: Decompose the given problem into smaller subproblems. Express
the solution of the original problem in terms of the solution for smaller
problems.
[Link] Structure: After solving the sub-problems, store the results to the sub
problems in a table. This is done because subproblem solutions are reused
many times, and we do not want to repeatedly solve the same problem over
and over again.
[Link]-up Computation: Using table, combine the solution of smaller
subproblems to solve larger subproblems and eventually arrives at a solution to
complete problem.
Bottom-up means:-
•Start with smallest subproblems.
•Combining their solutions obtain the solution to sub-problems of increasing
size.
•Until solving at the solution of the original problem.
 Components of Dynamic programming
1. Stages: The problem can be divided into several subproblems, which are called
stages. A stage is a small portion of a given problem. For example, in the
shortest path problem, they were defined by the structure of the graph.
2. States: Each stage has several states associated with it. The states for the
shortest path problem was the node reached.
3. Decision: At each stage, there can be multiple choices out of which one of the
best decisions should be taken. The decision taken at every stage should be
optimal; this is called a stage decision.
4. Optimal policy: It is a rule which determines the decision at each stage; a policy
is called an optimal policy if it is globally optimal. This is known as Bellman
principle of optimality.
5. Given the current state, the optimal choices for each of the remaining states
does not depend on the previous states or decisions. In the shortest path
problem, it was not necessary to know how we got a node only that we did.
6. There exist a recursive relationship that identify the optimal decisions for stage
j, given that stage j+1, has already been solved.
7. The final stage must be solved by itself.
 Development of DP Algorithm
• It can be broken into four steps:

1. Characterize the structure of an optimal solution

2. Recursive define the value of optimal solution

3. Compute the value of the optimal solution from the bottom up

(Starting with the smallest subproblem)

4. Construct the optimal solution for the entire problem from the
computed values of smaller sub-problems.
 Divide & Conquer Method vs Dynamic Programming.
Divide & Conquer Method Dynamic Programming

1. It deals (involves) three steps at each level 1. It involves the sequence of four steps:
of recursion: o Characterize the structure of optimal
• Divide the problem into a number of solutions.
sub-problems. o Recursively defines the values of
• Conquer the sub-problems by solving optimal solutions.
them recursively. o Compute the value of optimal solutions
• Combine the solution to the in a Bottom-up minimum.
sub-problems into the solution for original o Construct an Optimal Solution from
sub-problems. computed information.
2. It is Recursive. 2. It is non Recursive.
3. It does more work on subproblems and 3. It solves subproblems only once and then
hence has more time consumption. stores in the table.
4. It is a top-down approach. 4. It is a Bottom-up approach.
5. In this subproblems are independent of 5. In this subproblems are interdependent.
each other.
6. For example: Merge Sort & Binary Search 6. For example: Matrix Multiplication.
etc.
 Applications of DP
Applications of DP:

• Matrix chain multiplication

• 0/1 Knapsack problem
• All Pair Shortest Paths - Floyd-Warshall algorithm
• Single Source Shortest Path - Bellman-Ford algorithm

• Traveling Sales Person problem

• Longest Common Subsequence problem, etc.
 Matrix Multiplication
Matrix multiplication

Total Multiplications = 2 * 4 * 3 = 12

Matrix chain multiplication

Total Multiplications = 5* 5 * 4 *8 *2= 1600

 Matrix-Chain Multiplication
• Matrix chain multiplication problem:
1. Determine the optimal parenthesization of a product of n matrices.
2. Matrix chain multiplication is an optimization problem that to find
the most efficient way to multiply a given sequence of matrices.
The problem is not actually to perform the multiplications but
merely to decide the sequence of the matrix multiplications
involved.
• It is a Method under Dynamic Programming in which previous output is
taken as input for next.
• Here, Chain means one matrix's column is equal to the second matrix's
row [always].
• In general:
If A = ⌊aij⌋ is a p x q matrix
B = ⌊bij⌋ is a q x r matrix
C = ⌊cij⌋ is a p x r matrix
 Matrix-Chain Multiplication
In general:
If A = ⌊aij⌋ is a p x q matrix
B = ⌊bij⌋ is a q x r matrix
C = ⌊cij⌋ is a p x r matrix

Then

•Given following matrices {A1,A2,A3,...An} and we have to perform the matrix

multiplication, which can be accomplished by a series of matrix multiplications
In general, for 1≤ i≤ p and 1≤ j ≤ r

•It can be observed that the total entries in matrix 'C' is 'pr' as the matrix is of
dimension p x r Also each entry takes O (q) times to compute, thus the total time
to compute all possible entries for the matrix 'C' which is a multiplication of 'A'
and 'B' is proportional to the product of the dimension p q r.
 Matrix-Chain Multiplication:Problem Formulation
A product of matrices is fully parenthesized if it is either a single matrix or the
product of two fully parenthesized matrix products.
• For example, for the product ABCD, there are five possible ways to fully
parenthesize the product:
i. (A(B(CD))),
ii. (A((BC)D)),
iii. ((A(BC))D),
iv. ((AB)(CD)),
v. (((AB)C)D).
Example: Consider three matrices A10×100, B100×5, and C5×50
There are 2 ways to parenthesize
– ((AB)C) = D10×5 · C5×50
• AB ⇒ 10·100·5=5,000 scalar multiplications
• DC ⇒ 10·5·50 =2,500 scalar multiplications Total: 7,500
– (A(BC)) = A10×100 · E100×50
• BC ⇒ 100·5·50=25,000 scalar multiplications
• AE ⇒ 10·100·50 =50,000 scalar multiplications Total: 75,000
 Matrix-chain Multiplication
Matrix chain multiplication define recursive solution:
0, if i=j
m[i,j]=
mini(i≤k<j)(m[i, k]+m[k+1, j]+p[i-1] *p[k]* p[j]), if i<j

Algorithm: Matrix_chain_multiplication
► The following pseudo code assumes that –
• The matrix Ai has dimensions pi-1 x pi for i =1, 2, 3, 4, …. n.
• The input is a sequence (p0, p1, p2, …..pn) where length
[p]=n+1.
• The procedure uses an auxiliary table m[1..n, 1..n] for storing the
m[i,j] costs.
• An auxiliary table s[1..n, 1..n] that records which index of k
achieved the optimal cost in computing m[i,j].
 Matrix-chain Multiplication
Matrix_Chain_Order ( p[], n )

Steps:
1) for i🡨1 to n Do ►i=j
m[i,j]🡨0 ► since no product is required
2) for L🡨2 to n-1 do ►L is the chain length
for i🡨 1 to n - L Do
j🡨i+L -1
m[i,j] 🡨 ∞ ► INT_MAX
for k🡨 i to j-1 Do
q 🡨 m[i, k] + m[k+1, j] + p[i-1] * p[k] * p[j]
if q < m[i, j] Then
m[i, j] 🡨 q
s[I,j]🡨 k
3) Return m [1, n-1] and s
 Matrix-chain Multiplication
We will use table s to construct an optimal solution.
Constructing an Optimal Solution:

PRINT-OPTIMAL-PARENS (s, i, j)
1. if i=j
then print "A"
2. else print "("
PRINT-OPTIMAL-PARENS (s, i, s [i, j])
3. PRINT-OPTIMAL-PARENS (s, s [i, j] + 1, j)
4. print ")“
5. return
 MATRIX CHAIN MULTIPLICATION
Problem : Given five matrices A3x5, B5x15, C15x5, D5x10, E10x3. Find scalar
multiplication cost of given chain matrices.

Solution:
Matrix_Chain_Multi( p[], n )
► n is number of dimensions and p is the list of dimension
Steps: Here,
1) for i🡨1 to n Do ►i=j n = 6, and p[]={3, 5, 15, 5, 10, 3}
m[i, i]🡨0 ► number of multiplications are 0(zero) when there is only one matrix*/
2) for L🡨2 to n-1 do ►L is the chain length
for i🡨 1 to n - L Do i/j 1 2 3 4 5
j🡨i+L -1 1 0
m[i,j] 🡨 ∞ ► INT_MAX 2 0
for k🡨 i to j-1 Do 3 0
q 🡨 m[i, k] + m[k+1, j] + p[i-1] * p[k] * p[j] 4 0
if q < m[i, j] Then
5 0
m[i, j] 🡨 q
3) Return m [1, n-1]
m[1, 1] =m[2, 2] =m[3, 3]=m[4, 4] =m[5, 5]=0
 MATRIX CHAIN MULTIPLICATION
Solution: Matrix_Chain_Multi( p[], n )
Compute m[i][j] using ► n is number of dimensions and p is the list of dimension
m[i][j]=m[i][k] + m[k+1][j] + Pk-1 Pk Pj for k=I to j-1
Steps:
m[1][2]=m[1][1] + m[2][2] + P0 P1 P2=0 +0 + 3 . 5 . 15
=225 for k=1 1) for i🡨1 to n Do ►i=j
m[2][3]=m[2][2] + m[3][3] + P1 P2 P3=0 +0 + 5 . 15. 5 m[i, i]🡨0
=375 for k=2
2) for L🡨2 to n-1 do ►L is the chain length
m[3][4]=m[3][3] + m[4][4] + P2 P3 P4=0 +0 + 15 . 5 . 10
for i🡨 1 to n - L Do
=750 for k=3
j🡨i+L -1
m[4][5]=m[4][4] + m[5][5] + P3 P4 P5=0 +0 + 5 . 10. 3 m[i,j] 🡨 ∞ ► INT_MAX
=150 for k=4 for k🡨 i to j-1 Do
q 🡨 m[i, k] + m[k+1, j] + p[i-1] * p[k] * p[j]
i/j 1 2 3 4 5 if q < m[i, j] Then
m[i, j] 🡨 q
1 0 225 450
2 0 375 3) Return m [1, n-1]
3 0 750
4 0 150
5 0
 MATRIX CHAIN MULTIPLICATION
m[1][3]=min m[1][1] + m[2][3] + P0 P1 P3 Matrix_Chain_Multi( p[], n )
m[1][2] + m[3][3] + P0 P2 P3 ► n is number of dimensions and p is the list of dimensions
=450 for k=1 or 2, take k=1
Steps:
m[2][4]=625 for k=3
m[3][5]=375 for k=3 1) for i🡨1 to n Do ►i=j
m[1][4]=495 for k=3 m[i, i]🡨0

m[2][5]=600 for k=3 2) for L🡨2 to n-1 do ►L is the chain length

for i🡨 1 to n - L Do
m[1][5]=585 for k=4
j🡨i+L -1
:.The cost of scalar multiplication=585. m[i,j] 🡨 ∞ ► INT_MAX
for k🡨 i to j-1 Do
i/j 1 2 3 4 5 q 🡨 m[i, k] + m[k+1, j] + p[i-1] * p[k] * p[j]
if q < m[i, j] Then
1 0 225 450 495 585 m[i, j] 🡨 q
2 0 375 625 600
3) Return m [1, n - 1]
3 0 750 375

4 0 150

5 0
 MATRIX CHAIN MULTIPLICATION
Now apply Print-Optimal-Parens(s,i,j) to parenthesize A1 A2 A3 A5.
Initially, i=1 and j=5. i≠j, then k=s[1][5]=4, we have Print-Optimal-Parens(s,1,4)
and Print-Optimal-Parens(s,5,5).
Similarly, for Print-Optimal-Parens(s,1,4), i≠j, k=s[[1][4]=3, so
Print-Optimal-Parens(s,1,3) and Print-Optimal-Parens(s,4,4).
The process is shown below - i/j 1 2 3 4 5

S,1,5 1 0 1 1 3 4
2 0 2 3 3
3 0 3 3
S,1,4
S,5,5 4 0 4
5 0
S,1,3 A5
S,1,5

Start from last level A2 and A3 are

S,2,3 A4
S,1,1 multiplied 1st then A1 is multiplied with
(A2A3). proceeding in the same way, order
A1 of multiplication is (((A1(A2A3))A4)A5)
S,2,2 S,3,3

A2 A3
 MCQ
Which of the following methods can be used to solve the matrix chain
multiplication problem?
a) Dynamic programming
b) Brute force
c) Recursion
d) Dynamic Programming, Brute force, Recursion

Which of the following is the recurrence relation for the matrix chain multiplication
problem where mat[i-1] * mat[i] gives the dimension of the ith matrix?
a) dp[i,j] = 1 if i=j
dp[i,j] = min{dp[i,k] + dp[k+1,j]}
b) dp[i,j] = 0 if i=j
dp[i,j] = min{dp[i,k] + dp[k+1,j]}
c) dp[i,j] = 1 if i=j
dp[i,j] = min{dp[i,k] + dp[k+1,j]} + mat[i-1]*mat[k]*mat[j].
d) dp[i,j] = 0 if i=j
dp[i,j] = min{dp[i,k] + dp[k+1,j]} + mat[i-1]*mat[k]*mat[j].
 MCQ
Consider the two matrices P and Q which are 10 x 20 and 20 x 30 matrices
respectively. What is the number of multiplications required to multiply the
two matrices?
a) 10*20
b) 20*30
c) 10*30
d) 10*20*30

Consider the matrices P, Q, R and S which are 20 x 15, 15 x 30, 30 x 5 and 5 x

40 matrices respectively. What is the minimum number of multiplications
required to multiply the four matrices?
a) 6050
b) 7500
c) 7750
d) 12000
 MCQ
What is the time complexity of matrix chain multiplication implementation
using dynamic programming?
a) O(1)
b) O(n)
c) O(n2)
d) O(n3)

What is the space complexity of the matrix chain multiplication

implementation using dynamic programming?
a) O(1)
b) O(n)
c) O(n2)
d) O(n3)
 Assignments
• Problem_1
– Given the sequence {4, 10, 3, 12, 20, 7} of matrices and the sizes 4x10, 10x3,
3x12, 12x20, [Link] compute m[i,j], 0≤i, j≤5 and also given m[i,j]=0 for all i.
• ANS: Mini. Multi cost =1344 and Optimal sequence is ((A1 A2)((A3 A4)A5)).

• Problem_2:
– Given the four matrices P5 x 4, Q4 x 6, R6 x 2, T2 x 7. Find the optimal
sequence for the computation of multiplication operation.
• ANS: Mini. Multi cost=158 and Optimal sequence is ((P(QR))T)

• Problem_3:
– Given the four matrices A4 x 10, B10 x 3, C3 x 12, D12 x 20 ,E20 x 7. Find the
optimal sequence for the computation of multiplication operation.
• ANS: Mini. Multi cost =1344 and Optimal sequence is ((A B)((C D)E))
 References
• [Link]
• [Link]
• [Link]
• [Link]
 KNAPSACK PROBLEM
• Knapsack is basically means bag. A bag of given capacity.
• We want to pack n items in your luggage.
• The ith item is worth vi dollars and weight wi pounds.
• Take as valuable a load as possible, but cannot exceed capacity W
pounds.
• vi wi W are integers.
Input:
•Knapsack of capacity
•List (Array) of weight and their corresponding
value.

Output: To maximize profit and minimize weight

in capacity.

The knapsack problem where we have to pack

the knapsack with maximum value in such a
manner that the total weight of the items
should not be greater than the capacity of the
knapsack.
 TYPE OF KNAPSACK PROBLEM
• 0/1 Knapsack problem:
– Given a set of n items and Knapsack having capacity W such that each item
has some weight wi and value bi then the problem is to pack the Knapsack
in such a manner so that a maximum total value is achieved. The problem
said to be 0/1 Knapsack problem because the item from the list is either
rejected or accepted. It is an application of DP Techniques.
– It cannot be solved by the Greedy Approach because it is enable to fill the
knapsack to capacity.
– Greedy Approach doesn't ensure an Optimal Solution.

• Fractional Knapsack problem:

– Fractions of items can be taken rather than having to make a binary (1-0)
choice for each item. Fractional Knapsack problem is an application of
Greedy techniques. Fractional knapsack problem can be solved by Greedy
Strategy where as 0 /1 problem is not. It cannot be solved by Dynamic
Programming Approach.
 Example of 0/1 Knapsack Problem
• In 0/1 Knapsack Problem,
• As the name suggests, items are indivisible here.
• We can not take the fraction of any item.
• We have to either take an item completely or leave it completely.
• It is solved using dynamic programming approach.
 Example of 0/1 Knapsack Problem
Consider-
•Knapsack weight capacity = w
•Number of items each having some weight and value = n
•0/1 knapsack problem is solved using dynamic programming in the following
steps-
Step-01:
•Draw a table say ‘T’ with (n+1) number of rows and (w+1) number of columns.
•Fill all the boxes of 0th row and 0th column with zeroes as shown-
 Example of 0/1 Knapsack Problem
Step-02: Start filling the table row wise top to bottom from left to right.
•Use the following formula-
V [i, j] = max {T [i - 1, j], valuei + T [i - 1, j –weighti ]
•Here, T(i , j) = maximum value of the selected items if we can take items 1 to i
and have weight restrictions of j.
•This step leads to completely filling the table. Then, value of the last box
represents the maximum possible value that can be put into the knapsack.

Step-03: To identify the items that must be put into the knapsack to obtain that
maximum profit,
•Consider the last column of the table.
•Start scanning the entries from bottom to top.
•On encountering an entry whose value is not same as the value stored in the
entry immediately above it, mark the row label of that entry.
•After all the entries are scanned, the marked labels represent the items that
must be put into the knapsack.
 Time Complexity
• Each entry of the table requires constant time θ(1) for its
computation.
• It takes θ(nw) time to fill (n+1)(w+1) table entries.
• It takes θ(n) time for tracing the solution since tracing
process traces the n rows.
• Thus, overall θ(nw) time is taken to solve 0/1 knapsack
problem using dynamic programming.
 Problem Definition
For the given set of items and knapsack capacity = 5 kg, find the
optimal solution for the 0/1 knapsack problem making use of
dynamic programming approach.
Item Weight Value

1 2 3
2 3 4
3 4 5
4 5 6

OR
Find the optimal solution for the 0/1 knapsack problem making use of
dynamic programming approach. Consider-
n=4
w = 5 kg
(w1, w2, w3, w4) = (2, 3, 4, 5)
(v1, v2, v3, v4) = (3, 4, 5, 6)
 Problem Definition
OR
A thief enters a house for robbing it. He can carry a maximal weight
of 5 kg into his bag. There are 4 items in the house with the
following weights and values. What items should thief take if he
either takes the item completely or leaves it completely?
Item Weight (kg) Value ($)

Mirror 2 3
Silver
3 4
nugget
Painting 4 5
Vase 5 6
 Problem Solution
Given-

Knapsack capacity (w) = 5 kg

Number of items (n) = 4

Step-01:

Draw a table say ‘T’ with (n+1) = 4 + 1 = 5 number of rows and (w+1) = 5 + 1 =
6 number of columns.
Fill all the boxes of 0th row and 0th column with 0.
 Problem Solution
Step-02:

Start filling the table row wise top to bottom from left to right using the formula-
T (i , j) = max { T ( i-1 , j ) , valuei + T( i-1 , j – weighti ) }

Finding T(1,1)- Finding T(1,2)-

We have, We have,
i=1 i=1
j=1 j=2
(value)i = (value)1 = 3 (value)i = (value)1 = 3
(weight)i = (weight)1 = 2 (weight)i = (weight)1 = 2

Substituting the values, we get- Substituting the values, we get-

T(1,1) = max { T(1-1 , 1) , 3 + T(1-1 , 1-2) } T(1,2) = max { T(1-1 , 2) , 3 + T(1-1 , 2-2) }
T(1,1) = max { T(0,1) , 3 + T(0,-1) } T(1,2) = max { T(0,2) , 3 + T(0,0) }
T(1,1) = T(0,1) { Ignore T(0,-1) } T(1,2) = max {0 , 3+0}
T(1,1) = 0 T(1,2) = 3
 Problem Solution
Finding T(1,3)- Finding T(1,4)-

We have, We have,
i=1 i=1
j=3 j=4
(value)i = (value)1 = 3 (value)i = (value)1 = 3
(weight)i = (weight)1 = 2 (weight)i = (weight)1 = 2

Substituting the values, we get- Substituting the values, we get-

T(1,3) = max { T(1-1 , 3) , 3 + T(1-1 , 3-2) } T(1,4) = max { T(1-1 , 4) , 3 + T(1-1 , 4-2) }
T(1,3) = max { T(0,3) , 3 + T(0,1) } T(1,4) = max { T(0,4) , 3 + T(0,2) }
T(1,3) = max {0 , 3+0} T(1,4) = max {0 , 3+0}
T(1,3) = 3 T(1,4) = 3
 Problem Solution
Finding T(1,5)- Finding T(2,1)-

We have, We have,
i=1 i=2
j=5 j=1
(value)i = (value)1 = 3 (value)i = (value)2 = 4
(weight)i = (weight)1 = 2 (weight)i = (weight)2 = 3

Substituting the values, we get- Substituting the values, we get-

T(1,5) = max { T(1-1 , 5) , 3 + T(1-1 , 5-2) } T(2,1) = max { T(2-1 , 1) , 4 + T(2-1 , 1-3) }
T(1,5) = max { T(0,5) , 3 + T(0,3) } T(2,1) = max { T(1,1) , 4 + T(1,-2) }
T(1,5) = max {0 , 3+0} T(2,1) = T(1,1) { Ignore T(1,-2) }
T(1,5) = 3 T(2,1) = 0
 Problem Solution
Finding T(2,2)- Finding T(2,3)-

We have, We have,
i=2 i=2
j=2 j=3
(value)i = (value)2 = 4 (value)i = (value)2 = 4
(weight)i = (weight)2 = 3 (weight)i = (weight)2 = 3

Substituting the values, we get- Substituting the values, we get-

T(2,2) = max { T(2-1 , 2) , 4 + T(2-1 , 2-3) } T(2,3) = max { T(2-1 , 3) , 4 + T(2-1 , 3-3) }
T(2,2) = max { T(1,2) , 4 + T(1,-1) } T(2,3) = max { T(1,3) , 4 + T(1,0) }
T(2,2) = T(1,2) { Ignore T(1,-1) } T(2,3) = max { 3 , 4+0 }
T(2,2) = 3 T(2,3) = 4
 Problem Solution
Finding T(2,4)- Finding T(2,5)-

We have, We have,
i=2 i=2
j=4 j=5
(value)i = (value)2 = 4 (value)i = (value)2 = 4
(weight)i = (weight)2 = 3 (weight)i = (weight)2 = 3

Substituting the values, we get- Substituting the values, we get-

T(2,4) = max { T(2-1 , 4) , 4 + T(2-1 , 4-3) } T(2,5) = max { T(2-1 , 5) , 4 + T(2-1 , 5-3) }
T(2,4) = max { T(1,4) , 4 + T(1,1) } T(2,5) = max { T(1,5) , 4 + T(1,2) }
T(2,4) = max { 3 , 4+0 } T(2,5) = max { 3 , 4+3 }
T(2,4) = 4 T(2,5) = 7
 Problem Solution
Similarly, compute all the entries.
After all the entries are computed and filled in the table, we get the following
table-

The last entry represents the

maximum possible value that
can be put into the
knapsack.
So, maximum possible value
that can be put into the
knapsack = 7.

Identifying Items To Be Put Into Knapsack-

Following Step-04,
We mark the rows labelled “1” and “2”.
Thus, items that must be put into the knapsack to obtain the maximum value 7 are-
Item-1 and Item-2
 0/1 KNAPSACK ALGORITHM
0-1 knapsack problem: In the following, we have n kinds of items, 1 through
n. Each kind of item j has a value bj and a weight wj. We usually assume that
all values and weights are nonnegative. The maximum weight that we can
carry in the bag is W.
Algorithm: Dynamic-0-1-knapsack (b, w, n, W)
►The algorithm takes as input the maximum
weight W, the number of items n, and the two
sequences vb= <b1, b2, . . . , bn> and
► w = <w1, w2, . . . , wn>. It stores the B[i, j]
values in the table, that is, a two dimensional
array, B[0 . . n, 0 . . w] whose entries are computed
in a row-major order.
►That is, the first row of B is filled in from left to
right, then the second row, and so on. At the end of
the computation,
►B[n, w] contains the maximum value that can be
picked into the knapsack.
 0/1 KNAPSACK ALGORITHM
Algorithm: Dynamic-0-1-knapsack (b, w, Algorithm: FindKnapSackItem(B, w, n,
n, W) W)
Steps: ►B[n, W] stores the final solution as the
1) for w 🡨 0 to W do ►initia maximum value and the weight of the item
(i) B[0, w] 🡨 0 which is less than or equal to W
2) for i 🡨 1 to n do Steps:
(i) B[i, 0] 🡨 0 1) i🡨n
3) for w 🡨 1 to W do 2) k🡨W
(i) if wi ≤ w then ►item ‘i’ can be the 3) while i > 0 and k > 0 do
part of solution if B[i, k] ≠ B[i-1, k] then
(a) if bi + B[i-1, w-wi]>B[i-1,w] then mark the ith item as in the Knapsack
B[i, w] 🡨 bi + B[i-1, w-wi] i🡨i-1
(b) else k🡨k-wi
B[i, w] 🡨 B[i-1, w] else
(ii) else i🡨i-1
B[i, w] 🡨 B[i-1, w] ►wi > w 4) Return
4) return Example
Example
 0/1 KNAPSACK PROBLEM ANALYSIS
Analysis
for w = 0 to W do
B[0,w] = 0 O(W)
for i = 1 to n
B[i,0] = 0
for i = 1 to n do Repeat n times
for w = 0 to W do O(W)
< the rest of the code >
• The running time of the dynamic 0-1-kanpsack algorithm takes (n*W)
times.
The time complexity of the algorithm is O(n*W).
• The algorithm presented above only computes the maximum possible
value that can be taken in the Knapsack i.e. the value in B[n, W]. Now,
to choose the items that take part in making this maximum value i.e.
finding the actual Knapsack items.
 MCQ
The 0-1 Knapsack problem can be solved using Greedy algorithm.
a) True
b) False

The Knapsack problem is an example of ____________

a) Greedy algorithm
b) 2D dynamic programming
c) 1D dynamic programming
d) Divide and conquer

Which of the following methods can be used to solve the

Knapsack problem?
a) Brute force algorithm
b) Recursion
c) Dynamic programming
d) Brute force, Recursion and Dynamic Programming
 MCQ
You are given a knapsack that can carry a maximum weight of 60.
There are 4 items with weights {20, 30, 40, 70} and values {70,
80, 90, 200}. What is the maximum value of the items you can
carry using the knapsack?
a) 160
b) 200
c) 170
d) 90

For 0/1 KNAPSACK problem, the algorithm takes ________ amount of time for
memory table, and ______time to determine the optimal load, for N objects
and W as the capacity of KNAPSACK.
a) O(N+W), O(NW)
b) O(NW),O(N+W)
c) O(N),O(NW)
d) O(NW),O(N)
 MCQ
Which of the following problems is equivalent to the 0-1 Knapsack problem?
a)You are given a bag that can carry a maximum weight of W. You are given N
items which have a weight of {w1, w2, w3,…., wn} and a value of {v1, v2,
v3,…., vn}. You can break the items into smaller pieces. Choose the items in
such a way that you get the maximum value
b)b) You are studying for an exam and you have to study N questions. The
questions take {t1, t2, t3,…., tn} time(in hours) and carry {m1, m2, m3,….,
mn} marks. You can study for a maximum of T hours. You can either study a
question or leave it. Choose the questions in such a way that your score is
maximized
c)You are given infinite coins of denominations {v1, v2, v3,….., vn} and a sum S.
You have to find the minimum number of coins required to get the sum S
d)You are given a suitcase that can carry a maximum weight of 15kg. You are
given 4 items which have a weight of {10, 20, 15,40} and a value of {1, 2, 3,4}.
You can break the items into smaller pieces. Choose the items in such a way
that you get the maximum value
 Assignments
Problem_1: Consider a 0-1 Knapsack having weight capacity W=3 and
number of items are three such that S=3, wi = { 1, 2, 3} and vi = { 2, 3, 4}.
To computes the maximum possible value that can be taken in the
Knapsack i.e. the value in c[n, W] and also find the actual Knapsack
items.
Ans: S = {1, 2}, wi = { 1, 2}= {3} ≤ W and ci = { 2, 3} = {5}. Optimum value.
Problem_2: Given a Knapsack having maximum weight capacity W=4
and number of items available are three, such that S=3, wi={1, 3, 4} and
vi={3, 4, 5}. Fill the Knapsack such that Knapsack should not exceed its
maximum capacity and it should have maximum profit value.
Problem_3: Define how Knapsack problem is solved by using Dynamic
programming approach? Consider n=3, (w1, w2, w3)=(2, 3, 3), (p1, p2,
p3)=(1, 2, 4) and m=6. Find optimal solution for the given data.
 TRAVELLING SALESMAN PROBLEM using DP
Travelling Sales Person problem needs to visit ‘n’ cities in such a manner
that all the cities must be visited only once and in the end he returns to the
city from where he started with minimum distance.
Given a group of cities c={c1, c2, c3,…..cn}, where distance (i,j)
denotes the distance of travelling from city ci to city cj.

Given n cities and the distances dij between any two of them, we wish
to find the shortest tour going through all cities and back to the starting
city.

Usually the TSP is given as a G = (V,D) where V = {1, 2, . . . , n} is the set

of cities, and D is the adjacency distance matrix, with ∀ i, j εV, i≠ j, di,j > 0,
the problem is to find the tour with minimal distance weight, that starting in
1 goes through all n cities and returns to 1.

The TSP is a well known and difficult problem, that can be solved in O(n!)
≈O(nn e.n) steps.
Travelling Salesman problem using DP
TRAVELLING SALESMAN PROBLEM using DP

Cost matrix (Cij) =

1 2 3 4
1 0 10 15 20
2 5 0 9 10
3 6 13 0 12
4 8 8 9 0
TRAVELLING SALESMAN PROBLEM using DP
S=Φ
Cost(2,Φ,1)=d(2,1)=5Cost(2,Φ,1)=d(2,1)=5

Cost(3,Φ,1)=d(3,1)=6Cost(3,Φ,1)=d(3,1)=6

Cost(4,Φ,1)=d(4,1)=8Cost(4,Φ,1)=d(4,1)=8
TRAVELLING SALESMAN PROBLEM using DP
TRAVELLING SALESMAN PROBLEM using DP
TRAVELLING SALESMAN PROBLEM using DP
 SINGLE-SOURCE SHORTEST PATH PROBLEM
• Single-Source Shortest path problem to determine the shortest
paths from a given source vertex V1 to all the remaining vertices
of directed graph G(V, E, W).
• Given a directed weighted graph G(V,E,W), how we can find a
shortest path from given source vertex s to each other vertex v in
G.
• This problem can be solved easily with BFS Traversal algorithm
under the special case when all weights are 1.
• Bellman-Ford algorithm is preferable that follows Dynamic
Programming.
• Bellman-Ford algorithm can detect a cycle of negative weights if
the graph has an edge with negative weight.
• The Algorithm finds the shortest path repeating a vertex of a
graph.
 SINGLE-SOURCE SHORTEST PATH PROBLEM
Algorithm: Bellman_Ford(sp, G) 4. For i🡨1 to n-1 Do//Relaxation
►Where sp is a shortest path length in terms of 1. For j🡨1 to n Do
edge cost/weight and G(V, E, W) is a weighted 1. If W[i][j]≠0 or α Then
digraph. 1. X🡨sp[i]+W[i][j]
Steps: 2. If x < sp[j] Then
[Link] i🡨1 to n Do 1. Sp[j]🡨x
1. For j🡨1 to n Do 2. Pre[j]🡨i
1. If i=j then //self loop exists 5. For i🡨1 to n Do //Check negative wt.
1. W[i][j]🡨0 2. For j🡨1 to n Do
2. Else 1. If W[i][j]≠0 or α Then
1. If vi≠vj then //no edge 1. x🡨sp[i]+W[i][j]
1. W[i][j]🡨α 2. If x < sp[j] Then
2. Else 1. Return false
1. W[i][j]🡨W(vi,vj) 6. Return true.
[Link] i🡨1 to n Do
1. Sp[i]🡨α
2. Pre[i]🡨NULL
[Link][1]🡨0
 SINGLE-SOURCE SHORTEST PATH PROBLEM
Example: Find the shortest path using Bellman-Ford algorithm on
the digraph in given figure 1.

Figure 1: Directed Graph G(V, E, W)

 SINGLE-SOURCE SHORTEST PATH PROBLEM
Solution: Using steps of Bellman-Ford algorithm shortest path is-
Step 1: The cost/weight matrix for the given graph is -
V1 V2 V3 V4 V5
V1 0 10 α 5 α

W[i][j] = V2 α 0 1 2 α
V3 α α 0 α 6
V4 α 3 9 0 2
V5 7 α 4 α 0

Step 2: Initialize SP, Pre lists are

SP[i]={α, for all i=1 to 5},
Pre[i]={NULL, for all i=1 to 5},
SP[1]=0
SP values are encircled in the
corresponding vertices-
Fig 1. Initial solution Graph
 SINGLE-SOURCE SHORTEST PATH PROBLEM
Step 3: Make a list of edges ={(v1,v2), (v1,v4), (v2,v3), (v2,v3), (v2, v4), (v3,v5),
(v4,v2), (v4,v3), (v4,v5), (v5,v1), (v5, v3)}
In 1st pass we relax(visit) the edges with v1 as source. After relaxing the edges
(v1,v2) vertices to reach v2 and v4 from v1.
Cost are –
SP[2]=min{SP[2], SP[1]+W[1][2]}=min(α, 0+10)=10
SP[4]=min{SP[4], SP[1]+W[1][4]}=min(α, 0+5)=5

Similarly, after relaxing the next three

edges (v2, v3), (v2,v4), (v3,v5) and
computing corresponding costs.

Fig 2.
After relaxing the remaining edges
(v4, v2), (v4,v3), (v4,v5), (v5,v1),
(v5,v3) and computing corresponding
costs.

Fig 3.
 SINGLE-SOURCE SHORTEST PATH PROBLEM
Similarly, in 2nd pass relaxing
all the edges of the graph.

In 3rd and 4th passes there is

no change in the computation.
The fig. 5 shows the shortest
path length in terms of Fig 4.
cost/weight from vertex v1 as
source vertex to all other
vertices.

Fig 5.
 ALL PAIRS SHORTEST PATH PROBLEM
• All pairs shortest paths problem is to determine the shortest path
between all pair of vertices on a weighted digraph G (V, E, W).
• Solving all pair shortest path problem consists of computing the shortest
distance or path in terms of cost/weight between every pair of vertices
or nodes (u, v) where u, v € V in the graph G.
• We assume absence of negative or zero weight cycle.
 ALL PAIRS SHORTEST PATH PROBLEM
• Floyd-Warshall algorithm is to find the shortest path for all pair of
vertices.
• This algorithm in O(n3) time that uses Dynamic Programming.
• The cost/weight matrix of G is defined as
0, if i=j
W[i][j] = w, if i≠ j and (vi,vj) €E
α, if (vi,vj) €E
• The matrix is of n x n size since |V|=n, this will be the input to the
algorithm and corresponding output will also be an n x n cost matrix.
• The path matrix shows shortest path cost from vertex vi to vj and is
denoted by SPC[i][j].
Wij, if k=0
A Recursive definition is given by SPCij(k)=
min(SPCij(k-1), SPCik(k-1) + SPCkj (k-1)), ifk≥1
 ALL PAIRS SHORTEST PATH PROBLEM
Algorithm: Floyd_Warshall(G, SPC, n) Analysis:
►Where SPC is a matrix for shortest path cost , G(V, E, The Floyd-Warshall
W) is a weighted digraph and n is a |v|, no. of vertices. algorithm compares all
Steps: possible paths in the digraph
[Link] i🡨1 to n Do G between each pair of
1. For j🡨1 to n Do vertices.
2. SPC0 [i][j] 🡨W[i][j] It is possible to do this in n3
[Link] k🡨1 to n Do comparisons as obtained
1. For i🡨1 to n Do from step 2.
1. For j🡨1 to n Do Hence the required time
1. SPCij(k)=min(SPCij(k-1), SPCik(k-1) + SPCkj (k-1)) complexity for this algorithm
[Link] SPC(n). is O(n3).
 ALL PAIRS SHORTEST PATH PROBLEM
• Example: Find the shortest path between all pairs using
Floyd-Warshall algorithm on the weighted directed graph given
below – 2 3
V2 V3

7 5
V1
V1 V2 V3

Solution: V1 0 ∞ 5

The cost matrix of the given graph is W[i][j]= V2 7 0 3 =SPC 0[i][j]

V3 ∞ 2 0

Applying Floyd-Warshall algorithm, the problem can be sloved as follows –

For k=1,
SPCij(k)=min(SPCij(k-1), SPCik(k-1) + SPCkj (k-1))
SPC1[1][2]= min(SPC0[1][2], SPC0[1][1]+SPC0[1][2])=min(α, 0+ α)= α
SPC1[1][3]= min(SPC0[1][3], SPC0[1][1]+SPC0[1][3])=min(5, 0+ 5)= 5
SPC1[2][1]=min(7, 7+ 0)= 7
SPC1[2][3]=min(3, 7+ 5)= 3
SPC1[3][1]=min(α, α + 0)=α
SPC1[3][2]=min(2, 2+α)= 2
 ALL PAIRS SHORTEST PATH PROBLEM
For k=2
SPC2[1][2]=min(SPC1[1][2], SPC1[1][2]+SPC1[2][2]) =min(α, α+0)= α
SPC2[1][3] =min(5, α+5)= 5
SPC2[2][1]=min(7, 0+7)= 7
SPC2[2][3] =min(3, 0+3)= 3
SPC2[3][1] =min(α, 2+7)= 9
SPC2[3][2] =min(2, 2+0)= 2
For k=3
SPC3[1][2]=min(SPC2[1][2], SPC2[1][3]+SPC2[3][2]) =min(α, 5+2)=7.
SPC3[1][3] =min(5, 5+0)= 5
SPC3[2][1]=min(7, 3+9)= 7
SPC3[2][3] =min(3, 3+0)= 3 V1 V2 V3

SPC3[3][1] =min(9, 3+9)= 9 V1 0 7 5

SPC3[3][2] =min(2, 0+2)= 2 V2 7 0 3 = SPC3[i][j]

V3 9 2 0

This matrix shows the shortest paths between all pairs.

 MCQ
Which of the following standard algorithms is not Dynamic Programming
based.
(A) Bellman–Ford Algorithm for single source shortest path
(B) Floyd Warshall Algorithm for all pairs shortest paths
(C) 0-1 Knapsack problem
(D) Prim’s Minimum Spanning Tree

While finding optimal solution for a Travelling Salesman problem, sub-tours

are to be blocked because:
[Link] sub-tours cannot be found
[Link] sub-tours are not possible to cover
[Link] Salesman problem considers only some sub-tours, not all
iv. Travelling Salesman problem considers only complete tours, not sub-tours
 MCQ
Bellmann ford algorithm provides solution for ____________ problems.
a) All pair shortest path
b) Sorting
c) Network flow
d) Single source shortest path

What is the running time of Bellmann Ford Algorithm?

a) O(V)
b) O(V2)
c) O(ElogV)
d) O(VE)
 MCQ
How many times the for loop in the Bellmann Ford Algorithm gets executed?
a) V times
b) V-1
c) E
d) E-1

What is the basic principle behind Bellmann Ford Algorithm?

a) Interpolation
b) Extrapolation
c) Regression
d) Relaxation
 MCQ
Bellmann Ford Algorithm can be applied for _____________
a) Undirected and weighted graphs
b) Undirected and unweighted graphs
c) Directed and weighted graphs
d) All directed graphs

Consider the following graph. What is the minimum cost to travel from node
A to node C?
a) 5
b) 2
c) 1
d) 3
 References
• [Link]
• [Link]
• [Link]
• [Link]
• [Link]
• [Link]
Thank you !

H. Tunga 72