基于动态规划的游乐园调度

Question

您到达瓦尔多的世界游乐园，还有T分钟，直到公园关闭。公园有n次乘车，你的目标是在公园关闭前尽可能多地完成游乐。(对于此问题，使用相同的乘车次数可计算为2次。)给你一个W表，这样W(i，t)给你在时间t的等待时间，为了方便，假设t表示为公园关闭前的分钟。乘坐i本身需要里亚尔分钟，所有时间都是以整数分钟计算的。

我试着用一种类似于0 1背包问题的方法来解决它。但是表W包含了I的等待时间，它改变了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