Добрый день, не могу решить задачу Максимальная прибыль
Задача была изначально на англ. перевел и успел только заскринить. Подскажите путь для решения или тип задачи чтобы я мог порешать подобные задачи
Ответы (1 шт):
Автор решения: MBo
→ Ссылка
Попробуем так -
- выгоднее сначала дешёвые продавать, потом, когда категорий станет больше, продавать дорогие - это очевидно
- выгоднее сначала продать по одному предмету из каждой категории, чтобы следующие предметы из этой категории шли по максимальной цене - а вот мне это не вполне очевидно, как строго обосновать, однако проверка на случайных данных работает
Таким образом, выбираем из каждой категории минимальный элемент, сортируем их по возрастанию, считаем выгоду в этом порядке, потом добавляем сумму оставшихся цен, умноженную на количество категорий
[8, 13, 9, 20, 5, 3, 8, 15] price
[6, 5, 3, 1, 3, 6, 1, 5] category
тупой метод, перебирающий все перестановки (выгода, последовательность для лучшей выгоды)
297 [5, 4, 6, 1, 0, 2, 3, 7]
описанный алгоритм
297