递归回溯算法，用于解决分区问题 [英] Recursive-backtracking algorithm for solving the partitioning problem

问题描述

嘿，我正在寻找某种帮助，以找到一种将正数数组划分为k个部分的算法，以便每个部分(大约)具有相同的总和...假设我们拥有

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此算法应该像这样1,2,3,4,5 | 6,7 | 8,9对其进行分区元素的顺序无法更改...找到贪婪算法很容易，但是我正在寻找一个总是返回最佳解决方案的回溯版本...

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有任何提示吗?

Annyone got any hints ?

推荐答案

这里是一种不使用任何动态数据结构(例如列表)的解决方案.它们是完全不必要的，并且在实践中会使算法慢得多.

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.

让K为此处的分区数，让N为数组中元素的数量.

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

注意:这是O(n ^K )算法.它是次指数的，因为它不等同于一般的NP完全分区问题，在这里您正在寻找线性数组的连续段，而不是给定总集的任意子集.

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.

这篇关于递归回溯算法，用于解决分区问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！