Разбиение m элементов из отсортированного массива на n сегментов с приблизительно равными весами - PullRequest
Новая
       15

Разбиение m элементов из отсортированного массива на n сегментов с приблизительно равными весами

0 голосов
/ 22 июня 2019

Учитывая отсортированный массив с m элементами, сгруппируйте их в n сегментов с примерно равными весами.

Вот мой подход с использованием жадного алгоритма:

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

Итак, у меня есть собственный класс-оболочка с именем Bucket Container, в котором хранится список и сумма текущих элементов списка.У меня есть очередь с приоритетами, которая сначала опрашивает наименьшее количество сегментов.Итак, начиная с самого большого элемента, я опрашиваю наименее взвешенный сегмент и добавляю свой элемент в этот сегмент и повторно добавляю сегмент в очередь с приоритетами. 

class BucketContainer
   {
      private List<Integer> list;
      private int sum;

      BucketContainer()
      {
         sum = 0;
         list = new ArrayList<Integer>();
      }

      void add(int val)
      {
         sum += val;
         list.add(val);
      }

      List<Integer> getList()
      {
         return list;
      }

      int getSum()
      {
         return sum;
      }
   }

   public List<List<Integer>> partitionElements(int[] nums, int k)
   {
      PriorityQueue<BucketContainer> pq = new PriorityQueue<>((i1, i2) -> {return i1.getSum() - i2.getSum();});

      for (int i = 0; i < k; i++) {
         pq.add(new BucketContainer());
      }

      for (int i = nums.length - 1; i >= 0; i--) {
         BucketContainer lowestBucket = pq.poll();
         lowestBucket.add(nums[i]);

         pq.add(lowestBucket);
      }

      List<List<Integer>> result = new ArrayList();
      while (!pq.isEmpty()) {
         BucketContainer bucket = pq.poll();
         result.add(bucket.getList());
      }

      return result;
   }

Итак, это работает, если в данном массиве есть всеположительные целые числа, но не для массивов со смешанными целыми числами.

Если в массиве также есть и отрицательные значения, то текущее отрицательное число должно идти в сегмент с максимальным весом / суммой вместо блока с минимальной суммой (какэто сделало бы это ведро еще более менее взвешенным).Это было невозможно при использовании одной очереди приоритетов.

Как мы реализуем этот вопрос, обрабатывая как положительные, так и отрицательные случаи одновременно?

...