Минимизируйте стоимость покупки N элементов, используя заданный массив стоимости

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

Даны 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)

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