Максимизировать прибыль от m семян различных овощей в течение n дней подряд ⇐ Python

[Гость]

У меня есть матрица V размером m × n, где каждый элемент представляет прогнозируемые цены на m различных семян овощей для n подряд дни. Кроме того, существует целое число c (1 ≤ c ≤ n − 2). Мне нужно найти максимальную прибыль, которую можно получить от торговли семенами овощей, при условии, что я не могу купить семена в течение c дней после продажи семян любой марки. И я должен продать семя в инвентаре, прежде чем смогу купить другое. Если я продам семя в день i, мне не будет разрешено покупать семя до дня i + c + 1.

Ввод:

• Матрица V размеров m × n (1 ≤ m, n ≤ 1000), где каждый элемент V[j] (0 ≤ V[j ] ≤ (10000)) представляет прогнозируемую цену i-го начального числа в j-й день.

• Целое число 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)]

Объяснение:

Чтобы получить максимальную прибыль, купите 3-е семя в первый день, продайте его в день 3. купите 2-е семя в день 6 и продайте его в день 7, соблюдая двухдневный период ожидания.

Моя работа:

def find_max_profit(V, c): м, n = len(V), len(V[0]) максимальная_профит = 0 транзакции = [] # Создайте список для хранения максимальной цены через c + 1 дней для каждого дня. max_prices = [0] * n для i в диапазоне (n - 1, -1, -1): если я + с + 1 < n: max_prices = max(V[i + c + 1:], default=0) # Перебираем строки матрицы и для каждой строки находим максимальную разницу между ценой в текущий день и максимальной ценой через c + 1 дней. для меня в диапазоне (м): день_покупки, день_продажи = 0, 0 макс_дифф = 0 для j в диапазоне (n): если j > Sell_day + c: если V[j] - max_prices[j] > max_diff: max_diff = V[j] - max_prices[j] день продажи = j если V[j] < V[buy_day]: buy_day = j если max_diff > 0: транзакции.append((i + 1, buy_day + 1, Sell_day + 1)) макс_профит += макс_дифф возврат отсортированных (транзакции) В = [[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]] с = 2 вывод = find_max_profit(V, c) печать (выход) Я получаю вывод [(1, 6, 7), (2, 6, 7), (3, 1, 7), (4, 4, 5), (5, 4, 5) )]. Необходимый вывод: [(3, 1, 3),(2, 6, 7)], где c = 2.

Я выполняю следующие действия, чтобы получить максимальную прибыль:
[*]
Начните с входной матрицы V и целого числа c, как указано.
[*]
Для каждого дня j определите максимальную цену через c + 1 дней (т. е. в день j + c + 1 или позже), чтобы продать семя, купленное в день j.
[*]
Определите последовательность (i,j,l), которая дает максимальную потенциальную прибыль от продажи ith семени в l-й день, купленного в j-й день.