Максимизируйте сумму прибыли для N предметов так, чтобы прибыль для i-го предмета была произведением его веса и количества различных выбранных значений.

Учитывая массив arr[] , состоящий из N пар элементов как {значение, вес} , задача состоит в том, чтобы найти максимальную сумму прибыли, выбрав все данные N элементов так, чтобы прибыль от выбора i ^-го элемента вычислялась как произведение его веса и количества уже принятых различных значений.

Примеры:

Input: arr[] = {(1, 4), (2, 3), (1, 2), (3, 2)}
Output: 27
Explanation:
Below is the order of choosing items to maximize the profit:

• Choose the 2nd item i.e., arr[2] = (1, 2). The profit for the current chosen item is 2 * 1 = 2.
• Choose the 3rd item i.e., arr[3] = (3, 2). The profit for the current chosen item is 2 * 2 = 4.
• Choose the 1st item i.e., arr[1] = (2, 3). The profit for the current chosen item is 3 * 3 = 9.
• Choose the 0th item i.e., arr[0] = (1, 4). The profit for the current chosen item is 4 * 3 = 12.

Therefore, the total profit is 2 + 4 + 9 + 12 = 27, which is maximum among all possible combination of chosen N pairs.

Input: arr[] = {(2, 2), (1, 2), (3, 2)}
Output: 12

Подход: Данная проблема может быть решена с использованием жадного подхода. Идея состоит в том, чтобы отсортировать данный массив arr[] по весу элементов, и сначала выбираются все отдельные элементы, а затем оставшиеся элементы. Выполните следующие шаги, чтобы решить данную проблему:

• Инициализируйте набор, скажем, items , чтобы хранить все уникальные элементы.
• Инициализируйте переменную, скажем, uniqCnt = 0 , чтобы хранить количество уникальных элементов.
• Инициализируйте переменную, скажем, maxProfit = 0 , чтобы сохранить общую максимальную прибыль.
• Инициализируйте переменную, скажем, totWeight = 0 , чтобы хранить общий вес элементов, которые не уникальны.
• Пройдите по массиву arr[] и сохраните все уникальные элементы в set items .
• Отсортируйте массив arr[] в порядке возрастания их весов.
• Сохраните количество уникальных элементов как uniqCnt = items.size() и удалите все элементы из элементов.
• Пройдите по заданному массиву arr[] и проверьте следующее условие:
  • if(!items.count(arr[i].first)) если это окажется правдой, то вставьте элемент arr[i].first в набор элементов, рассчитайте прибыль и обновите ее до maxProfit с помощью maxProfit += items.size() * arr[i].second .
  • В противном случае обновите totWeight как totWeight += arr[i].second .
• Рассчитайте прибыль для элементов, которые не уникальны, и обновите maxProfit как maxProfit += totWeight * uniqCnt .
• После выполнения вышеуказанных шагов выведите значение maxProfit как результирующую максимальную прибыль.

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

Сложность по времени : O(N*logN), так как мы используем функцию сортировки.

Вспомогательное пространство : O(N), так как мы используем дополнительное пространство.