algorithm - 游乐园使用动态规划安排游乐设施

你到达沃尔多世界游乐园时，离公园关闭还有T分钟公园有n个游乐设施，您的目标是在公园关闭前尽可能多地完成游乐设施（对于这个问题，同一次乘坐两次算作两次乘坐。）给你一张表W，这样W（i，t）就给了你在时间t时乘坐i的等待时间。为了方便起见，假设t表示为停车场关闭前的分钟骑行i本身需要ri分钟，所有时间都是以整数分钟计算的。
我试着用类似于01背包问题的方法来解决它。但是包含等待乘坐时间i的表W随时间t的变化而变化。它是一个背包加活动选择的组合问题吗？

最佳答案

这有什么意义吗让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

关于algorithm - 游乐园使用动态规划安排游乐设施，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/48757785/