Минимальная цена, необходимая для получения N предметов заданных типов

Даны целые числа X , Y и Z , представляющие цены 3 предметов A, B и C соответственно, и два целых числа a и b , обозначающие количество предметов двух типов. Задача состоит в том, чтобы вычислить минимальную цену, необходимую для получения N предметов типа A, B или C , где A требует 2 предметов типа a , B требует 3 предметов типа b , а C требует 1 предмета типа a и 1 предмета. типа б .

Примеры:

Input: X = 300, Y = 200, Z = 100, N = 4, a = 3, b = 7
Output: 500
Explanation: Four items can be formed by buying 3 C’s (3*100 = 300) using 3 a’s and 3 b’s, and 1 B(1*200 = 200) using 3 b’s. Final price = 300 + 200 = 500, which is minimum possible.

Input: X=300, Y=150, Z=200, N=5, a=6, b=4
Output: 1100

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

• Инициализируйте переменную, скажем, minimum_bill , чтобы хранить минимальную цену, необходимую для покупки N предметов.
• Итерация по диапазону C , меньшему или равному N .
• Инициализируйте переменные, скажем, maxorders_A равно (a – orders_C)/2 , а maxorders_B равно (b – orders_C)/3.
• Проверьте, меньше ли maxorders_A + maxorders_B + maxorders_C , чем N , затем продолжите.
• Если X меньше Y , тогда найдите заказы_A как min(maxorders_A, N — заказы_C) и заказы_B как N — заказы_C — заказы_A .
• В противном случае найдите заказы_B как min(maxorders_B, N — заказы_C) и заказы_A как N — заказы_C — заказы_B .
• Рассчитайте требуемый счет в переменной, скажем , счет, как (X * заказы_A) + (Y * заказы_B) + (Z * заказы_C) .
• В каждой итерации обновляйте Minimum_bill как минимум из Minimum_bill и bill .

Ниже приведена реализация вышеуказанного подхода:

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