股票利润最大化：给定价格数组，如何用边界实现利润最大化

Question

我一直在尝试编写一些基于“Maximizing profit for given stock quotes”的代码，但是我想对交易者可以做的事情施加一些限制。在我的代码中，我试图将他可以拥有的股票数量限制为N=4，而他在给定的时间间隔内可以买卖的股票数量是C=1。我们的目标是为给定的股票价格数组找到一组最终实现利润最大化的操作。你知道吗

对于给定的价格数组

stock_prices = [20,20,20,20,25,30,25,30,25,20,20,30,35,40,45,50,60,60,50,40,35,30,25,20],

最理想的情况是，交易者应该在时间间隔1、2、3和4买入（每个20美元），在时间间隔6和8卖出（每个30美元），在10和11买入，在16、17、18和19卖出所有的东西。在一天结束时，交易者应该没有股票。你知道吗

这是我迄今为止尝试过的：

def calcprofit(stock_prices):
    buy=[1]*len(stock_prices) # 1 reflects buy and 0 reflects sell
    profit=0
    m=0
    storage_limit = 4
    c = 1   #Change in shares
    storage = 0
    for i in reversed(range(len(stock_prices))):
        price = stock_prices[i] # shorthand name
        if storage < storage_limit and m <= price:
            buy[i] = 1
            m = price
            storage += c
        if storage >= storage_limit and m >= price:
            buy[i] = 0
            storage -= c
        profit += (m-price)
    return (profit,buy,storage)

目前该代码不能一次卖出一只股票，也不能卖出或买入一个数量决定的变动。目前，我得到的结果是：

(505, [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0], 3)

此外，但不是必要的，而不是使用一个二进制系统作为链接上面显示的买卖，有可能引入另一个整数来显示交易者持有（既不买也不卖）？你知道吗

Answer 1

您可以使用动态规划来计算最佳利润，如下所示：

stock_prices = [20,20,20,20,25,30,25,30,25,20,20,30,35,40,45,50,60,60,50,40,35,30,25,20]
MAX_STOCKS = 4
memory = {}

def dp(i=0, stockes=0):

  if i == len(stock_prices):
    return 0

  if (i, stockes) in memory:
    return memory[(i, stockes)]

  memory[(i, stockes)] = max(
      dp(i+1, stockes), 
      dp(i+1, stockes+1) - stock_prices[i] if stockes < MAX_STOCKS else -1, 
      dp(i+1, stockes-1) + stock_prices[i] if stockes > 0 else -1)

  return memory[(i, stockes)]


print(dp())

输出：

160

160与您描述的最佳解决方案匹配。有关解决方案的两个重要注意事项：

1. 在每次通话中，我都会计算出三种可能性：不买入或卖出，如果未达到上限就买入一只股票，如果我们至少有一只股票，就卖出一只股票。你知道吗
2. 在动态规划中，问题具有重叠结构，子问题多次出现，因此我使用memorydic来记忆反复出现的子问题。你知道吗