Максимальная прибыль при покупке и продаже акций не более k раз [DP] - PullRequest
0 голосов
/ 26 января 2020

Здесь есть алгоритм, использующий Dynami c Программирование, чтобы найти максимальную прибыль, покупая и продавая акцию не более k раз. Я изменил алгоритм для возврата всей 2D-матрицы (транзакции k * дней n), и вот пример:

def maxProfit(price, n, k):

    # Table to store results of subproblems
    # profit[t][i] stores maximum profit
    # using atmost t transactions up to
    # day i (including day i)
    profit = np.zeros((k + 1, n)) 

    # Fill the table in bottom-up fashion
    #for i in range(1, k + 1):
    prevDiff = np.zeros(k) + float('-inf')

    for j in range(1, n):
        temp = prevDiff
        prevDiff = np.maximum(prevDiff, profit[0:k, j - 1] - price[j - 1])
        profit[1:k + 1, j] = np.maximum(profit[1:k + 1, j - 1], price[j] + prevDiff)

    return profit
# Driver Code
if __name__ == "__main__": 

    price = [100, 99, 0, 5, 6, 50, 100, 35, 33, 0, 70, 1000, 500, 400, 0, 225, 700, 2000, 800]
    k = 3
    n = len(price)
    profit = maxProfit(price, n, k)
    print("Maximum profit is:")
    print(profit)

Вывод:

[   0.    0.    0.    0.    0.    0.    0.    0.    0.    0.    0.    0.     0.    0.    0.    0.    0.    0.    0.]  
[   0.    0.    0.    5.    6.   50.  100.  100.  100.  100.  100. 1000.  1000. 1000. 1000. 1000. 1000. 2000. 2000.]  
[   0.    0.    0.    5.    6.   50.  100.  100.  100.  100.  170. 1100.  1100. 1100. 1100. 1225. 1700. 3000. 3000.]  
[   0.    0.    0.    5.    6.   50.  100.  100.  100.  100.  170. 1100.  1100. 1100. 1100. 1325. 1800. 3100. 3100.]  

Мой вопрос Как вы можете определить, в каких парах дней (i, j) (покупка в день i, продажа в день j) имели место транзакции?

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...