PROBLEM SET




 

One important thing that I should tell you at this point, the problems of dynamic programming are little tough and lengthy. They need the complete understanding of this programming method plus a lot of time to think. So, go through these problems only after completing the earlier lessons.

Don't lose your confidence with that statement, just go through these problems and look for the hints provided by me if needed.

PROBLEM 1.
There is class in which (m X n) students are present where m are the rows and n are the columns. Each student is having some different numbers of toffees. Now each student (i,j) where i is the row number and j is the column number can take the toffees from student(i+1,j-1) , student(i+1,j) , student(i+1,j-1). Now you have to find an order(of toffee passing from higher order rows to lower order rows ) such that among the persons in the first row, one gets the maximum number of toffees (out of all possible passing of toffees).
PROBLEM 2.
There is a matrix (m X n) which is filled with the integers. Now you have to find out the smallest possible matrix (sub-part of that matrix) with maximum sum of the integers values in that selected sub-part of the main matrix.

PROBLEM 3.
This is known as a Matrix Chain Multiplication problem. In this we have to minimize the numbers of calculations that are performed in a matrix multiplication. For example we have to multiply A1,A2,A3,A4,A5,A6. These six matrices can be multiplied as follows:-
(((A1A2)(A3A4A5)A6)
((A1A2A3A4)A5A6)
And so on……..different combinations are possible.
But we have to find a way in which the calculations are minimum, by calculation it means that to multiply two matrices A[p][q] and B[q][r] we need to perform (p*q*r) many operations.


Do NOT follow this link or you will be banned from the site!

Non-profit Tax ID # 203478467