连续n天从m种不同的蔬菜种子中获得最大利润

Question

我有一个维度为

m × n

的矩阵 V，其中每个元素代表连续

m

天内

n

不同蔬菜种子的预测价格。另外，还有一个整数

c (1 ≤ c ≤ n − 2)

。我需要找到通过交易蔬菜种子可实现的最大利润，但受到限制，即在出售任何品牌种子后

c

天内不能购买任何种子。如果我在第

i

天出售种子，则在第

i + c + 1

天之前我不能购买任何种子。

输入：

• 维度为

m × n (1 ≤ m, n ≤ 1000)

的矩阵 V，其中每个元素

V[i][j] (0 ≤ V[i][j] ≤ (10000))

代表

i-th

种子在

j-th

天的预测价格。

• 一个整数

c (1 ≤ c ≤ n − 2)

，表示出售种子后购买其他品牌种子之前的等待时间。

输出：

返回表示交易的元组序列

(i, j, l)

，其中：

•

i (1 ≤ i ≤ m)

是所选种子的索引。

•

j1 (1 ≤ j1 ≤ n)

是我购买种子以在这次交易中获得最大利润的日子。

•

j2 (1 ≤ j2 ≤ n)

是我出售种子以在这次交易中获得最大利润的日子。

~~~~例子~~~~

如果

c = 2

和5X7矩阵

V

是：

[[2,9,8,4,5,0,7],
 [6,7,3,9,1,0,8],
 [1,7,9,6,4,9,11],
 [7,8,3,1,8,5,2],
 [1,8,4,0,9,2,1]]

预期输出为:

[(3, 1, 3),(2, 6, 7)]

解释：

为了获得最大利润，请在第 1 天购买第 3 个种子，在第 3 天出售它。在第 6 天购买第 2 个种子，在第 7 天出售，遵守 2 天的等待期。

我的作品：

def find_max_profit(V, c):
    m, n = len(V), len(V[0])
    max_profit = 0
    transactions = []

    # Create a list to store the maximum price after c + 1 days for each day.
    max_prices = [0] * n
    for i in range(n - 1, -1, -1):
        if i + c + 1 < n:
            max_prices[i] = max(V[i][i + c + 1:], default=0)

    # Iterate over the rows of the matrix, and for each row, find the maximum difference between the price on the current day and the maximum price after c + 1 days.
    for i in range(m):
        buy_day, sell_day = 0, 0
        max_diff = 0

        for j in range(n):
            if j > sell_day + c:
                if V[i][j] - max_prices[j] > max_diff:
                    max_diff = V[i][j] - max_prices[j]
                    sell_day = j

            if V[i][j] < V[i][buy_day]:
                buy_day = j

        if max_diff > 0:
            transactions.append((i + 1, buy_day + 1, sell_day + 1))
            max_profit += max_diff

    return sorted(transactions)


V = [[2,9,8,4,5,0,7],
     [6,7,3,9,1,0,8],
     [1,7,9,6,4,9,11],
     [7,8,3,1,8,5,2],
     [1,8,4,0,9,2,1]]
c = 2

output = find_max_profit(V, c)
print(output)

我得到了

[(1, 6, 7), (2, 6, 7), (3, 1, 7), (4, 4, 5), (5, 4, 5)]

的输出。所需的输出是

[(3, 1, 3),(2, 6, 7)]

，其中

c = 2

。

我遵循以下步骤以获得最大利润：

1. 从输入矩阵 V 和整数

   c

   开始。

2. 对于每一天

   j

   ，确定

   c + 1

   天后（即第

   j + c + 1

   日或更晚）出售在

   j

   日购买的种子的最高价格。

3. 通过在第 l 天出售在

   (i,j,l)

   天购买的

   ith

   种子，确定产生最大潜在利润的序列

   jth

   。

Answer 1

这是我到目前为止的想法，我还没有时间实现和测试：动态程序的每个单元格可以有两种概念状态：买入或卖出。

如果是购买：

dp[row]["buy"][col] =
  -price + (
    max(dp[any_row]["sell"][col'])
      where col' < col - c
    or 0 if none
  )

我们可以将最好的

max(dp[any_row]["sell"][col'])

保留到

col - c - 1

以供查找。

如果是卖出：

dp[row]["sell"][col] =
  price + max(dp[row]["buy"][col'])
    where col' < col
or 0 if none

我们可以将每行最好的

max(dp[row]["buy"][col']

保留到

col - 1

。

由于我们总是查看前面的列，因此我们可以逐列处理矩阵。

结果应该是：

max(dp[any_row]["sell"][col])
  where col ≤ last column
or 0 if none

后者我们可以边走边保存。