Dynamic Programming 7 (Matrix Chain Multiplication)
Matrix chain multiplication is another classic dynamic programming problem where we need to figure out how to multiply some matrix using the fewest number of operations. This problem is a very good example of divide and conquer method.
I hope everyone knows how to multiply matrices, I won’t go into detail about it. I just want to remind you of a few properties.
and A2 and their dimensions are (r1×c1) and (r2×c2).
And A2 can be multiplied only if c1=r2
Either, that is, the columns of the first matrix must be equal to the rows of the second matrix.
The order of the matrix is important. A1×A2
Not the same thing.
The matrix is two times (A1×A2).
After doing this the new matrix we get will have dimension (r1×c2)
While multiplying matrices we have to multiply and add some numbers which we can call scalar multiplication. We have to multiply the total scalar by (r1×c1×c2)
times Because the new matrix will have (r1×c2) cells and c1 in each cell
Must be multiplied to get that.
Now let us consider the product of 3 matrices A1×A2×A3
have to figure out Now col1=row1 and col2=row3
Only then we can do the quality.
The only difference between the two methods is the bracketing. In both cases we have row1×col3
Get a matrix of dimensions. But do we need to multiply the same numerical scalar both ways? Let’s see an example.
Assume the dimensions of the matrices are (10×100), (100×5) respectively.
The scalar multiplication in bracketing is (10×100×5)+(10×5×50)=7500
scalar multiplication in bracketing is (100×5×50)+(10×100×50)=75000
The second way is to create a huge matrix by multiplying (A_2 \times A_3) at the beginning and increase the complexity by 10 times.
As you can see our objective now is to minimize the number of scalar multiples. you n
Given a matrix, say the minimum number of scalar multiplication operations using A1×A2×…..×An−1
can be extracted
Now the first task is to find the subproblem. Assume that the subproblem is f(i)
That is, we need to find the minimum number of operations required to multiply i to n−1th matrices. Now suppose we bracket the i to kth matrix and f(k+1)
I will solve the problem recursively.
How to optimally multiply th matrix?
Our function f
Empty works for the part from i to the end of the array, not for [i,j] in any subarray. So what can be done? We redefine the function: f(i,j). Now we take any position k
For this we can divide Areta into two parts.
For example, n=4
K can be divided into:
Bracketing -> (A0)×(A1×A2×A3) Subproblem -> f(0,0)+f(1,3)
Bracketing -> (A0×A1)×(A2×A3) Subproblem -> f(0,1)+f(2,3)
Bracketing -> (A0×A1×A2)×(A3) Subproblem -> f(0,2)+f(3,3)
That is, we divide the array into two parts as much as possible and solve the subproblems recursively, each k
The subproblems for this will be f(i,k) and f(k+1,n−1)
The matrices are divided into two but the work is not finished, now we have to merge. k
Dividing by the th position gives you a matrix of size rowi×colk on the left and rowk+1×colj on the right where colk=rowk+1. Now these two matrices have to be multiplied and the operation rowi×colk×colj is required
Writing the row-columns of the th matrix as mat[i].row and mat[i].col gives the recursive formula:
Divide and conquer has 2 main tasks, defining and merging right and left subproblems. We can write a clearer formula if we treat the merge operation as a separate function:
If you keep this pattern in mind, you can solve many more problems.
Our number of subproblems is O(n2).
and running a loop of size n on each subproblem. Total complexity is O(n3)
If you like before i
And try to iterate by running two nested loops of j, then it will not work this time. mem table but this time row-by-row buildup is not happening. Now we solve for the smallest subarrays first eg (0,0),(1,1),(2,2), then for subarrays of size 1, eg (0,1),(1,2). In this way we will solve all the subproblems of size 1 to n. Then the table will now build up like this:
I have shown in which order the table has been built up in the picture.
Once you figure out the ordering of loops in iterative DP, the rest is the same as recursive. I used the evaluate function instead of directly accessing the mem table to handle the corner case.
You have learned to solve coin change in several ways, so I will not solve 0-1 knapsack. I will tell you what the problem is and give some hints.
Bangla for knapsack is bag or bag. You have a bag that has a certain capacity, let’s say that capacity is C.
. Now you have n items in front of you, each item has a fixed price and weight. The following image is taken from wikipedia:
Now you have to say the maximum value of items you can put in the bag. The reason for saying “0-1” knapsack is that if you take something, you have to take it whole, you can’t break it in half. If there is a breaking rule, the problem is called fractional knapsack. In case of fractional, taking the expensive items first gives optimum results, 0-1 knapsack will not work.
Here two arrays P and W will be given as input. The i-th object has price Pi and weight Wi
Our subproblem will be the same as before f(i,C)
Which means starting from i to n−1
Maximum profit with th items. From there we have two choices
If the th item is not filled in the bag, then the next subproblem is f(i+1,C)
Taking the th item, the next subproblem is f(i+1,C–Wi)
We have to take the larger of the two. In the 2nd case the profit will be Pi
, must also be added.
Your task will be to write recursive and iterative versions of this formula and optimize the memory of the iterative version.
So far today. By now you have learned many tricks of dynamic programming, now if you solve more problems you will master it. The problems you’ve seen so far involve maximizing or minimizing the result, then we’ll look at some combinatorics problems.
You must Join our Facebook Group and Subscribe YouTube Channel
All Links in Below:
Join Our FreeWebsiteCreate Facebook Group to get an instant update for projects, templates, design resources, and solutions.
Join Our YouTube Channel & Subscribe with Bell Icon for New Video:
Join Our Official Facebook Page For the Latest updates All Code Projects are Free:
Visit our service page to get premium services.
You must Join our Facebook Group and Subscribe YouTube Channel