Минимальная сумма денег, необходимая для покупки товаров с учетом кэшбэка

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

Дан массив arr[] длины N, обозначающий стоимость N предметов и кэшбэк при покупке этого предмета. Задача состоит в том, чтобы найти минимальную сумму денег, необходимую для покупки всех предметов, независимо от порядка их покупки.

Примеры:

Input: arr[] = [ [ 7, 2 ], [ 10, 5 ], [ 2, 1] ] 
Output: 16
Explanation: The geek can buy the goodies in the following ways:
[7, 2] ->  [10, 5] -> [2, 1]  minimum money required are 15.
Initially 15. After buying the first element (15-7+2) = 10.
After buying the second element (10-10+5) = 5.
After buying the third item (5-2+1) = 4.
If anything less than 15 was used then one would not have enough money
to buy the second item. Similarly for the following cases
[7, 2] -> [2, 1] -> [10, 5] minimum money required is 16
[10, 5] -> [7, 2] -> [2, 1] minimum money required is12
[10, 5] -> [2, 1] -> [7, 2] minimum money required is 13
[2, 1] -> [7, 2] -> [10, 5] minimum money required is 16
[2, 1] -> [10, 5] -> [7, 2] minimum money required is 13
In the worst case, geek requires 16 unit of money

Input: arr[] = [ [ 5, 6 ], [40, 2], [89, 8] ]
Output: 127

Наивный подход: чтобы решить проблему, следуйте следующей идее:

Generate all the ways possible and find the minimum money required for each permutation.

Временная сложность: O(N*N!)
Вспомогательное пространство: O(N)

Эффективный подход. Эту проблему можно решить, используя следующее наблюдение:

  • Calculate the effective amount of money spent on items where the price ≥ refund. Effective amount spend = price – refund. 
  • Calculate the maximum price among those items where the refund > price. Effective amount spend = price of most expensive item.
  • Add refund from the last transaction because we cannot use refund from the last transaction to reduce effective amount spend. 
    • Last transaction in worst case will be either having maximum refund such that price of that item > refund. 
    • Otherwise, last transaction will have maximum cost if refund on purchasing that item is greater than its price.

Выполните шаги, указанные ниже, чтобы реализовать вышеуказанную идею:

  • Перебрать массив от i = 0 до N-1 :
    • Добавьте эффективную стоимость.
    • На каждой итерации вычисляйте максимальное значение, полученное в последней транзакции в худшем случае, используя идею, упомянутую выше.
  • В конце добавьте максимальную стоимость последней транзакции в худшем случае к общей эффективной стоимости, чтобы получить требуемый ответ.

Ниже приведена реализация вышеизложенной идеи.

Временная сложность: O(N)
Вспомогательное пространство: O(1)

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