Алгоритм рекурсивного обращения для решения проблемы разделения

Question

Эй, я ищу помощь, чтобы найти алгоритм, который делит множество положительных чисел на K-части, чтобы каждая часть имела (приблизительно) ту же сумму ... допустим, у нас есть

1,2,3,4,5,6,7,8,9 en k = 3 thn Алгоритм должен разделить его, как это 1,2,3,4,5 | 6,7 | 8,9 Орден Элементы не могут быть изменены ... найти жадный алгоритм легко, но я ищу версию отступа, которая всегда возвращает оптимальное решение ...

У Аннене есть какие -либо подсказки?

Answer 1

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

Пусть k - это количество раздела здесь и n - количество элементов в вашем массиве.

int start[K];

void register() {
   /* calculate the error between minimum and maximum value partitions */
   /* partition boundaries are start[0], start[1], start[2], ... */
   /* if lower error than previously stored, remember the best solution */
}

void rec(int s, int k) {
  if (k == K) register();
  for (int i = s; i < N; i++) {
    start[k] = i;
    rec(i + 1, k + 1);
  }
}

/* entry */
start[0] = 0;
rec(1, 1);
/* then output the best solution found at register() */

Примечание: это O (n^K) алгоритм. Это субэкспоненциальный, потому что это нет эквивалентно общей проблеме разделения NP, вы ищете смежные сегменты линейного массива вместо произвольных подмножеств с данным общим набором.

Answer 2

Что вы имеете в виду под оптимальным решением? Я считаю, что вы имеете в виду тот, который минимизирует сумму каждого расстояния раздела до оптимального разделения. Оптимальным разделом будет раздел, который его элементы сумма равной общей сумме, разделенной количество разделов.

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

void FindPartitions(int[] numbers, int i, IList<int>[] partitions, int currentPartition, IList<int>[] bestSolution, ref int minDistance)
{
    if (i == numbers.Length)
    {
        int sum = numbers.Sum();
        int avg = sum / partitions.Length;
        int currentDistance = 0;
        foreach (var partition in partitions)
            currentDistance += Math.Abs(partition.Sum() - avg);
        if (currentDistance < minDistance)
        {
            minDistance = currentDistance;
            for (int j = 0; j < partitions.Length; j++)
                bestSolution[j] = new List<int>(partitions[j]);
        }
    }
    else
    {
        partitions[currentPartition].Add(numbers[i]);
        FindPartitions(numbers, i + 1, partitions, currentPartition, bestSolution, ref minDistance);
        partitions[currentPartition].RemoveAt(partitions[currentPartition].Count - 1);
        if (currentPartition < partitions.Length - 1)
            FindPartitions(numbers, i, partitions, currentPartition + 1, bestSolution, ref minDistance);
    }
}

Answer 3

Вот рекурсивный алгоритм в JavaScript. Эта функция возвращает итоги, которые будет назначен каждый работник. Допустим, книжные нагрузки на массивы входных входных классов-это множество положительных чисел, которые вы хотите разделить как можно более справедливо на K-частях (скажем, среди работников K)

Вот рабочая скрипка:https://jsfiddle.net/missyalyssi/jhtk8vnc/3/

function fairWork(bookLoads, numWorkers = 0) {
    // recursive version

    // utilities
    var bestDifference = Infinity;
    var bestPartition = {};
    var initLoads = {};
    var workers = Array.from({length: numWorkers}, (val, idx) => {
      initLoads[idx] = 0;
      return idx;
    });
    var bookTotal = bookLoads.reduce((acc, curr) => {return acc + curr}, 0); 
    var average = bookTotal / bookLoads.length;

    // recursive function
    function partition(books = bookLoads, workers, loads={}) {

      // if only one worker give them all the books
      if (workers.length == 1 && books.length > 0) {
        var onlyWorker = workers[0];
        loads[onlyWorker] += books.reduce((acum, curr, idx, arr) => {
                               return acum + curr;
                             },0);
        books = [];
      }

      // base case
      if (books.length == 0) {
        var keys = Object.keys(loads);
        var total = 0;
        for (let key = 0; key < keys.length; key++) {
          // square so that difference shows 
          total += Math.pow(Math.abs(average - loads[keys[key]]), 2);
        }
        if (total < bestDifference) {
          bestDifference = total;
          bestPartition= loads;
        }
        return bestPartition;
      }

      var currBookLoad = books[0];

      // add book to curr worker 1
      var newWorker1Loads = Object.assign({}, loads);
      var worker1 = workers[0]; 
      newWorker1Loads[worker1] = newWorker1Loads[worker1] + currBookLoad || currBookLoad;
      partition(books.slice(1), workers, newWorker1Loads)

      // give to next worker
      var newNextWorkerLoads = Object.assign({}, loads);
      var worker2 = workers[1]; 
      newNextWorkerLoads[worker2] = newNextWorkerLoads[worker2] + currBookLoad || currBookLoad;
      partition(books.slice(1), workers.slice(1), newNextWorkerLoads)

      return bestPartition;
    }
    // function call
    return partition(bookLoads, workers, initLoads)
}
fairWork([3,1,2,3], 3)
//Result will be: Object {0: 3, 1: 3, 2: 3}
fairWork([1,2,3,4,5,6,7,8,9], 3)
//Result will be: Object {0: 15, 1: 13, 2: 17}