使用动态编程的游乐园调度骑行

Question

您到达Waldo的世界游乐园，剩下T分钟，直到公园关闭。公园有N游乐设施，您的目标是在公园关闭之前完成尽可能多的游乐设施。(对于这个问题，乘坐相同的骑行时间为2次骑行。(给您一个桌子W，以便W(i，t(为您提供等待时间i在时间t。为了方便起见，假设T表示为公园关闭前几分钟。骑行本身需要RI分钟，所有时间都在整数分钟内测量。

我尝试使用类似于0 1背包问题的方法来解决它。但是桌子W包含乘车的等待时间，我将wrt变成了时间t。它是一个背包加活动选择的合并问题吗？

Answer 1

这是否有意义？令f(t)代表时间t上最可实现的骑行。然后：

// Higher t is back in time
// since t is how many minutes
// before the park closes
f(t) = max(
  // Not taking any ride
  f(t - 1),
  // Take ride i
  1 + f(t - W(i, t) - r_i)
)
for all i