Разделить массив на K непересекающихся подмножеств так, чтобы максимальная сумма всех подмножеств была минимальной

Опубликовано: 22 Сентября, 2022

Дан массив arr[] , состоящий из N целых чисел и целого числа K , задача состоит в том, чтобы разбить данный массив на K непересекающихся подмножеств так, чтобы максимальное из суммы всех подмножеств было минимальным.

Примеры:

Input: arr[] = {1, 7, 9, 2, 12, 3, 3}, M = 3
Output: 13
Explanation:
One possible way to spit the array into 3 non-overlapping subsets is {arr[4], arr[0]}, {arr[2], arr[6]}, and {arr[1], arr[5], arr[3]}.
The sum of each subset is 13, 12 and 12 respectively. Now, the maximum among all the sum of subsets is 13, which is the minimum possible sum.

Input: arr[] = {1, 2, 3, 4, 5}, M = 2
Output: 8

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

  • Инициализируйте Min-Heap, используя Priority_queue, скажем, PQ , чтобы хранить сумму элементов каждой группы.
  • Повторите в диапазоне [1, K] и вставьте 0 в PQ .
  • Отсортируйте массив arr[] в порядке убывания.
  • Пройдите по массиву arr[] и для каждого элемента массива arr[i] добавьте элемент arr[i] в наименьшую группу сумм, которая будет находиться наверху приоритетной очереди PQ .
  • После выполнения вышеуказанных шагов выведите последний элемент приоритетной очереди PQ как результирующую минимизированную максимальную сумму среди всех возможных групп.

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

+++++

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

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