算法 - 在一定时间间隔内买卖股票的最佳方式

Question

有人给了我一个教科书上的问题，我想不出来。它是:

假设您有一只股票 STOK，您准备将所有资金投资一个月(0...30 天)，在月底您可以'持有任何股票。你有 m 钱。在任何一天 d，STOK 的价格都是 p(d)，在任何一天您都可以买卖股票。但是，l(d)，您一天可以买卖多少股票是有限制的(买卖相同)。如果需要，您可以购买非整数单位的股票，以便于计算。鉴于这些功能，您如何安排采购计划来最大化您的利润？

天真的解决方案:在以下限制条件下，每天尽可能多地购买股票:如果您无法在卖出日期之前卖出所有股票，则不要再买入；如果你没钱了，就不要再买了。当你到达必须开始卖出股票的点时(这是众所周知的，因为你提前知道股票价格)然后每天尽可能多地卖出。但是，此解决方案不起作用，因为如果股票在月初下跌然后在前五天后飙升怎么办？

这听起来像动态规划，但股票价格不是单调的事实使它变得困难。考虑到问题的持续性，蛮力显然已经过时了。有什么解决办法吗？

Answer 1

如果您提前知道股票价格，这听起来很像递归(蛮力)中的问题。您构建了一个包含每日股价、每日限制、每日手头现金和每日持有股票的数组。使用接受每个数组作为参数的递归函数。选择未标记的可能的一对日期，标记一个买入和一个卖出，更新所有数组，执行适当的限制并递归，如果月底的现金大于起始现金，将数组集保存为新的最大值，将数组重置为起点，选择下一对天并继续直到尝试完所有。