6

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

  • 设 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
4

2 回答 2

10

让我们代表您在第一次考试中S[i][j]花费时间单位可以获得的最佳分数。您可以通过查看的每个值来计算。对于 的每个元素，请记住前一行中给出最佳结果的值。及时学习所有考试的最佳分数的答案是公正的，您可以使用您记住的值来确定每次考试花费多少时间。jiS[i][j]S[i-1][k]kSkTS[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
于 2012-11-23T20:43:24.470 回答
2

我假设你的问题中的 vy G 和 M 是同一个意思，如果你根本不花任何时间参加考试，你会得到 0 分。

在这种情况下，我将 DP 矩阵定义为 D[i,t] = 通过在从 0 到 i 的考试子集上花费 t 个总单位时间可获得的最佳分数。

Wlog 您可以假设矩阵的第一列全为 0。

在这种情况下，您可以观察到 D 满足以下递归：

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

这是您应用动态规划所需要的

于 2012-11-23T20:58:55.760 回答