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

Опубликовано: 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)