Минимальная сумма денег, необходимая для покупки товаров с учетом кэшбэка
Дан массив 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 moneyInput: 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)