Максимальная прибыль при использовании M денег и снижении половины стоимости не более чем K акций

Опубликовано: 25 Февраля, 2023

Учитывая стоимость [] и прибыль [] 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 = 37

Input:  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)

Статьи по Теме:

  • Введение в массивы — учебные пособия по структуре данных и алгоритмам
  • Введение в динамическое программирование — учебные пособия по структурам данных и алгоритмам

РЕКОМЕНДУЕМЫЕ СТАТЬИ