使用动态编程实现最大化

Question

我试图找出类似于以下问题的解决方案:

• 设M是n行和T列的矩阵.
• 让每一行都有正的非递减值.(例如row = [1,2,30,30,35])
• 设M [i] [j]对应于通过在考试i上花费j个时间单位而获得的分数.

使用动态规划,解决问题,找到花费T单位时间学习的最佳方式,这将获得最高的总分.

在此先感谢任何帮助:)

我的尝试:

S[][] = 0

for i = 1:n
   for j = 0:T
       max = 0
       for k = 0:j
           Grade = G[i][j]+ S[i-1][T-k]
           if Grade > max
              max = Grade
       end for
       S[i][j] = max
    end for
end for

Answer 1

让我们S[i][j]代表您j在第一次i考试中花费时间单位的最高分.您可以S[i][j]通过查看S[i-1][k]每个值来计算k.对于每个元素S,请记住k上一行中给出最佳结果的值.对于及时学习所有考试的最佳分数的答案T是正确的S[n][T],您可以使用k您记住的值来确定每次考试花费的时间.

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 j-k time on the previous exams.
           Grade = S[i-1][j-k] + M[i][k]
           if Grade > max
              max = Grade
       end for
       S[i][j] = max
    end for
end for