Geek Answers Handbook

Maximization using dynamic programming

I am trying to find a solution for a problem similar to the following:

  • Let M be a matrix of n rows and T columns.
  • Let each row have positive non-decreasing values. (for example, string = [1, 2, 30, 30, 35])
  • Let M [i] [j] correspond to the result obtained by spending j units of time in exam i.

Using dynamic programming, solve the problem to find the best way to spend T units of time studying that will give the highest overall score.

Thanks in advance for any help :)

My attempt:

S[][] = 0 for i = 1:n for j = 0:T max = 0 for k = 0:j Grade = G[i][j]+ S[i-1][Tk] if Grade > max max = Grade end for S[i][j] = max end for end for
+6
source share
2 answers

Let S[i][j] represent the best result for which you can spend j units of time in the first exams i . You can calculate S[i][j] by looking at S[i-1][k] for each value of k . For each element of S remember the value of k from the previous line, which gave the best result. The answer to the fact that the best result to study all exams at a time T is just S[n][T] , and you can use the k values ​​you remembered to determine how much time to spend on each exam.

 S[][] = 0 for j = 0:T S[0][j] = M[0][j] for i = 1:n for j = 0:T max = 0 for k = 0:j # This is the score you could get by spending j time, spending # k time on this exam and jk time on the previous exams. Grade = S[i-1][jk] + M[i][k] if Grade > max max = Grade end for S[i][j] = max end for end for
+10
source

I assume that vy G and M in your problem you mean the same thing, and that you get 0 points if you do not spend any time on the exam.

In this case, I would define the DP matrix as D [i, t] = the best result achievable by spending t full units of time on a subset of exams from 0 to i.

Wlog, you can assume that the first column of the matrix is ​​equal to all 0s.

In this case, you may notice that D satisfies the following repetition:

  • D [0, t] = M [0, t]
  • D [i, t] = max_ {0 <= k <= t} (M [i, k] + D [i-1, tk])

what you need to apply dynamic programming

+2
source

More articles:


All Articles