algorithm - 使用动态规划最大化

Question

我正在尝试为类似于以下的问题提出解决方案:

• 令 M 为 n 行 T 列的矩阵。
• 让每一行都有正的非递减值。 (例如行 = [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] 表示您在第一个 i 考试中花费 j 时间单位可以获得的最好成绩。您可以通过查看 S[i-1][k] 的每个 k 值来计算 S[i][j]。对于 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