Минимизируйте стоимость покупки N элементов, используя заданный массив стоимости
Даны 2 массива num[] и cost[] , содержащие количество элементов и стоимость покупки такого количества элементов соответственно. {т.е. cost[i] — это стоимость покупки num[i] элементов}. Задача состоит в том, чтобы минимизировать затраты на покупку ровно N элементов.
Примеры:
Input: num[] = [1, 2, 10, 50], cost[] = [400, 750, 3250, 15000], N = 7
Output: 2650
Explanation: The minimum amount needed to buy 7 pizzas is 2650.
You can order 3 units of 2 pizzas and 1 unit of 1 pizza.Input: num[] = [1, 2, 10, 50], cost[] = [400, 750, 3250, 15000], N = 15
Output: 5150
Explanation: The minimum amount needed to buy 15 pizzas is 5150.
You can order 1 unit of 10 pizzas, 2 units of 2 pizzas and 1 unit of 1 pizza.
Подход: проблему можно решить с помощью рекурсии, основанной на следующей идее:
For each element of the num, we are having two choices whether to include that particular combo or not.
- Case 1: When the elements present at num[i] gets include in final result, the cost to these will get add up in our total cost and the total elements will get reduced by the number of pizzas brought.
- Case 2: When the element in num present at num[i] does not get included in final result, no cost will get add up in our total cost.
You can include elements if and only if the elements at num[i] is less than or equal to the total available.
Следуйте шагам, указанным ниже, чтобы реализовать идею:
- Создайте рекурсивную функцию.
- Для каждого вызова есть два варианта выбора элемента, как указано выше.
- Вычислите значение всех возможных случаев, как указано выше.
- Минимум среди них и есть требуемый ответ.
Ниже приведена реализация вышеуказанного подхода:
Временная сложность: O(2 N )
Вспомогательное пространство: O(N)
Эффективный подход (с использованием мемоизации):
Мы можем использовать динамическое программирование для хранения ответов на перекрывающиеся подзадачи. Мы можем сохранить результат для текущего индекса и оставшегося количества элементов в матрице DP.
Состояния ДП можно представить следующим образом:
DP[current index][remaining elements]
Ниже приведена реализация вышеуказанного подхода:
Временная сложность: O(len*N), где len — длина массива.
Вспомогательное пространство: O(len*N)
Эффективный подход (с использованием табуляции):
Поскольку мы знаем, что решение для мемоизации можно дополнительно оптимизировать с помощью метода табуляции, и мы можем уменьшить вспомогательное пространство стека, занимаемое решением для мемоизации.
Состояния DP остаются прежними:
DP[current index][remaining elements]
Ниже приведена реализация вышеуказанного подхода:
Временная сложность: O(len*N), где len — длина массива.
Вспомогательное пространство: O(len*N)