动态规划最大化

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

- Pi_

Answer 1

让S [i] [j]表示在前 i 次考试上花费 j 单位时间可以达到的最佳分数。您可以通过查看每个k的S [i-1] [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

- Vaughn Cato

---

你能用伪代码的形式表达这个想法吗？我一直在尝试写类似的东西，但是我自己都搞混了，结果一无所获... - Pi_

@Pi_：你能在你的问题中添加一个你尝试过的例子吗？ - Vaughn Cato

我理解了，谢谢！（有一个小错别字，应该是 for j = 0:T）。 - Pi_

@VaughnCato，for i = 1:n（其中矩阵索引基于0）并不是迭代一个n行的矩阵，而是一个n+1行的矩阵。for j = 0:T同理，这是一个T+1列的矩阵。 :) - vladr

@vladr: 对。也许原问题中的 M 矩阵旨在成为一个 T+1 的列矩阵。 - Vaughn Cato

Answer 2

我假设你在问题中提到的vy G和M是相同的意思，并且如果你不花任何时间参加考试，你将得到0分。

在这种情况下，我会将DP矩阵定义为D [i，t] =在0到i的一部分考试上花费t总单位时间可实现的最佳分数。

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

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

• D [0，t] = M [0，t]
• D [i，t] = max_ {0 <= k <= t}（M [i，k] + D [i-1，t-k]）

这就是您需要应用动态规划的内容

- Giro Tonti