Recursive-backtracking algorithm for solving the partitioning problem

Question

Hey, i'm looking for some help to find an algorithm which divides an array of positive numbers into k-parts so that each part has the (approximately) the same sum ... let's say we have

1,2,3,4,5,6,7,8,9 en k=3 thn the algorithm should partition it like this 1,2,3,4,5|6,7|8,9 the order of the elements cannot be changed ... Finding a greedy algorithm is easy but i'm looking for a backtracking version which always returns the optimal solution ...

Annyone got any hints ?

Answer 1

Here is a solution that doesn't use any dynamic data structures such as lists. They are totally unnecessary and would in practice make the algorithm much slower than necessary.

Let K be the number of partitions here and N be the number of elements in your array.

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() */

Note: this is an O(n^K) algorithm. It is sub-exponential because this is not equivalent to the general NP-complete partitioning problem has here you are looking for contiguous segments of a linear array instead of arbitrary subsets of a given total set.

Answer 2

What do you mean by optimal solution? I believe you mean the one that minimizes the sum of each partition distance to the optimum partition. The optimum partition would be the partition that it's elements sum is equal to the total sum divided the number of partitions.

If you don't mind about efficiency, then maybe this rough approach is good enough for you. I haven't tested the algorithm to check it's correctness, so be careful.

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);
    }
}