用于解决分区问题的递归回溯算法

Question

嘿,我正在寻找一些帮助来找到一个算法,将一组正数分成k部分,这样每个部分都有(大约)相同的总和...让我们说我们有

1,2,3,4,5,6,7,8,9 zh k = 3算法应该像这样划分它1,2,3,4,5 | 6,7 | 8,9的顺序元素无法更改...找到一个贪婪的算法很容易,但我正在寻找一个总是返回最佳解决方案的回溯版本...

Annyone得到了什么提示？

Answer 1

最佳解决方案是什么意思？我相信你的意思是最小化每个分区距离到最佳分区的总和.最佳分区是它的元素总和等于总和除以分区数的分区.

如果你不介意效率,那么这种粗略的方法对你来说就足够了.我没有测试算法来检查它的正确性,所以要小心.

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 2

这是一个不使用任何动态数据结构(如列表)的解决方案.它们完全没有必要,并且实际上会使算法比必要的慢得多.

设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完全分区问题,在这里你要寻找线性数组的连续段而不是给定总集的任意子集.