Войти Регистрация
Алгоритмы

93. Бюджет на продвижение объявлений

Сложная

У продавца на Авито несколько объявлений. Для объявления i доступны пакеты продвижения packages[i] = [[цена, просмотры], ...]: например, «x2 на 7 дней» и «x10 на 7 дней».

На каждое объявление можно купить не больше одного пакета или ни одного. Бюджет — budget рублей. Верните максимальное суммарное число дополнительных просмотров.

В работе: Выбор по одному варианту из каждой группы под общий лимит: тарифы, конфигурации серверов, пакеты услуг.

Пример 1

Ввод
packages = [[[100, 300], [250, 900]], [[150, 500]], [[50, 100], [300, 1000]]]
budget = 400
Вывод
1400

250 + 150 = 400 рублей: 900 + 500 = 1400 просмотров.

Пример 2

Ввод
packages = [[[500, 900]]]
budget = 300
Вывод
0

Денег не хватает ни на что.

Ограничения

  • 1 ≤ число объявлений ≤ 100
  • 1 ≤ пакетов у объявления ≤ 10
  • 1 ≤ цена ≤ budget ≤ 10⁴
  • 1 ≤ просмотры ≤ 10⁵
  • Лимит — 2 с на тест (2000 мс).
Как вызывается ваш код Читать ввод и печатать ответ не нужно: мы вызываем функцию на каждом тесте и сравниваем то, что она вернула. print() и console.log() уходят в консоль. 
def max_promo_views(packages, budget):
ДПРюкзак по группамРюкзак с ограничениямицельn2

Источник: наша задача на данных Авито. Условие пересказано своими словами.