Максимальная прибыль при использовании M денег и снижении половины стоимости не более чем K акций
Учитывая стоимость [] и прибыль [] N акций и K билетов, задача состоит в том, чтобы найти максимальную общую прибыль, которую можно получить от начальной суммы M денег, используя K билетов.
Примечание. Билет можно использовать для снижения стоимости любой акции до половины первоначальной цены, а для конкретной акции билет можно использовать только один раз.
Примеры:
Input: N = 3, cost[] = {2, 4, 5}, profit[] = {20, 17, 15}, K = 1, M = 4
Output: 37
Explanation: The most optimal case is when we take the 1st stock at regular cost and use a ticket for 2nd item. Total amount of money spent = (2 + (4 / 2)) = 4 ≤ M. Total Profit obtained is = 20 + 17 = 37Input: N = 3, cost[] = {4, 4, 3}, profit[] = {12, 14, 7}, K = 2, M = 5
Output: 26
Explanation: The most optimal case is when we take the 1st stock using the 1st ticket and the 2nd item using the 2nd ticket. Total amount of money spent = ((4 / 2) + (4 / 2)) = 4 ≤ M. Total Profit obtained is = 12 +14 = 26
Наивный подход: реализуйте приведенную ниже идею, чтобы решить проблему:
It is always beneficial to use the maximum number of tickets because it will reduce the price of the stock. For each item there are 3 choices:
- Don’t consider the current stock.
- Take the current but don’t use the ticket.
- Take the current and use the ticket.
Были предприняты шаги для решения проблемы:
- Инициализируйте целочисленную переменную An для хранения максимальной полученной прибыли.
- Чтобы рассмотреть все подмножества элементов, для данного элемента у нас есть 3 варианта:
- Не берите текущую акцию, тогда текущая оставшаяся сумма будет M , Ans останется прежней.
- Если возможно (M ≥ cost[i]) , возьмите текущую акцию и добавьте значение ее прибыли к Ans , тогда текущие оставшиеся деньги будут равны M – cost[i] .
- Если билет используется, добавьте значение его прибыли к Ans , тогда текущие оставшиеся деньги будут M – cost[i]/2 .
- Возвращает максимальный An из трех возможных случаев.
Ниже приведена реализация кода вышеуказанного подхода.
Временная сложность = O(3 N )
Вспомогательное пространство = O (1)
Эффективный подход с использованием динамического программирования:
The above approach has overlapping subproblems as can be seem below. Say:
M = 5, N = 3, K = 2, Cost[] = {4, 4, 3}, Profit[]={ 12, 14, 7}
Let X(M, 0, K) represent the given state that M initial money and K tickets and at index 0:
- Left move – 1st case – Don’t take current element
- Down move – 2nd case – Take the current element
- Right move – 3rd case – Take the current element with Ticket.
The recursion tree for the test case
So we can use the concept of dynamic programming.
Следуйте шагам, указанным ниже, чтобы реализовать идею:
- Инициализируйте трехмерный массив (скажем, dp[][][] ) для хранения значения каждого состояния, как показано выше.
- Теперь используйте ту же рекурсию, что и в предыдущем подходе.
- Чтобы сократить вычисление, если встречается состояние, которое уже рассчитано, верните максимальную прибыль для этого состояния.
- Значение, сохраненное в состоянии (M, 0, K), является требуемым ответом.
Ниже приведена реализация эффективного подхода.
Временная сложность: O(N*M*K)
Вспомогательное пространство: O(N*M*K)
Статьи по Теме:
- Введение в массивы — учебные пособия по структуре данных и алгоритмам
- Введение в динамическое программирование — учебные пособия по структурам данных и алгоритмам