所需的算法- benelux竞赛2007

Question

这个问题(最后一个)出现在2007年比荷卢算法编程竞赛中

http://www.cs.duke.edu/courses/cps149s/spring08/problems/bapc07/allprobs.pdf

问题陈述简而言之：

一家公司需要找出策略，在给定的投入下，何时购买或出售或不操作，以实现利润最大化。输入的格式为：

6
4  4  2
2  9  3
....
....

这意味着输入时间为6天。

第一天:你得到4股，每股价格4美元，最多只能卖出2股。

第二天:你得到2股，每股9美元，最多你可以卖出3股。

。

我们需要输出能够实现的最大利润。

我正在思考如何去解决这个问题。在我看来，如果我们使用暴力，它将花费太多的时间。如果这可以转化为像0-1背包这样的DP问题？我们将非常感谢您的帮助。

Answer 1

它可以通过DP来解决

假设有n天，股票总数为m

设fi意味着在第i天，剩余j股的情况下，最大利润为fi。

显然，fi=maximum(fi-1+k*price_per_dayi)，0<=k<=maximum_shares_sell_per_dayi

它可以进一步优化，因为fi只依赖于fi-1，所以这里可以使用滚动阵列。因此，您只需定义f2即可节省空间。

总时间复杂度为O(n*m*maximum_shares_sell_per_day)。

也许它可以进一步优化以节省时间。欢迎任何反馈

Answer 2

您的描述与PDF中的最后一个问题不太匹配-在PDF中，您会收到第一列中指定的股票数量(或者被迫购买-因为没有决定让它变得无关紧要)，并且只能决定卖出多少股票。既然它没有说明，我假设卖空是不允许的(否则忽略除了价格之外的一切，在衍生品市场上赚这么多钱，以至于你可以贿赂SEC或国会，然后退休：-)。

这看起来像一个动态程序，其中每个时间点的状态都是您手中的股票总数。所以在时间n，你有一个数组，每个元素对应于你当时可能持有的股票数量，在这个元素中，你可以赚到最大的钱，同时得到这个数量的股票。因此，你可以为time n+1计算出同样的信息。当你到达终点时，你所有的股票都一文不值，所以最好的答案是与最大金额相关的那个。

Answer 3

我们不能比在价格最高的一天卖出最大数量的股票更好，所以我在想：(这可能很难(有效地)实现)

计算到目前为止每天收到的股票总数可能是一个好主意，以提高算法的效率。

按价格降序处理天数。

对于一天，sell amount = min(daily sell limit, shares available) (对于最大价格日(第一个处理日)，可用股份=到目前为止收到的股份)。

在随后的所有日子里，shares available -= sell amount。对于前几天，我们对(shares available - shares sold)和从该日期到刚处理的日期之间的所有条目进行二进制搜索= 0。

我们可能不需要物理地设置这些值(至少不是在每一步)，只需要根据到目前为止的历史动态计算它们(我认为是区间树或类似的东西)。