优化子集求和实现

我正在使用下面的代码研究子集求和问题的变体的解决方案。 该问题需要从较大的集合（超集）生成11个int的子集，并检查它是否与特定值（endsum）匹配。

#include  #include  #include  int endsum = 0, supersetsize = 0, done = 0; int superset[] = {1,30,10,7,11,27,3,5,6,50,45,32,25,67,13,37,19,52,18,9}; int combo = 0; int searchForPlayerInArray(int arr[], int player) { for (int i=0; i<11; i++) { if (arr[i] == player) { return 1; } } return 0; } int sumOfArray(int arr[]) { int res = 0; for (int i=0; i<11; i++) { res+=arr[i]; } return res; } void printArray(int arr[], int arrSize) { for (int j=0; j<arrSize; j++) { printf("%2d ",arr[j]); } printf("= %d\n",endsum); } void permute(int subset[], int pos, int sspos) { if (done) { //when a correct solution has been found, stop recursion return; } if (sspos == supersetsize) { // out of possible additions return; } if (pos == 11) { //is the current subset 11 ints long? int res = sumOfArray(subset); combo++; if (res == endsum) { //if the sum of the array matches the wanted sum, print printArray(subset,11); done = 1; } return; } for (int i=sspos; i<supersetsize; i++) { //assert(pos < 11); //assert(i+1 <= supersetsize); subset[pos] = superset[i]; permute(subset,pos+1,i+1); } } int main(void) { endsum = 110; supersetsize = 20; int *arr; arr = malloc(supersetsize*sizeof(int)); int i; for (i=0; i<supersetsize; i++) { arr[i] = 0; } permute(arr,0,0); printf("Combinations: %d",combo); return 0; } 

尽管这种解决方案适用于小型超集（<15），但它速度慢且效率低，因为它会产生所有可能的排列，而不仅仅是唯一的排列。 如何优化它以仅生成唯一的子集？

编辑：由流行需求添加的完整源代码。

Answer 1

仅生成唯一子集的一种方法是按顺序添加超集中的元素，并使用其他参数permute （例如， supersetPos ）以指示您在超集中的位置。 这会生成排序的排列，这些排列将是唯一的。

编辑 ：AFAIK在您的样本上正确运行的代码：

 #include  int superset[] = { 1, 30, 10, 7, 11, 27, 3, 5, 6, 50, 45, 32, 25, 67, 13, 37, 19, 52, 18, 9 }; int supersetsize = 20; int endsum = 110; int done = 0; int sumOfArray(int array[]) { int sum = 0; for(int i = 0; i < 11; i++) sum += array[i]; return sum; } void permute(int subset[], int pos, int sspos) { if (pos == 11) { //is the current subset 11 ints long? if (sumOfArray(subset) == endsum) { //if the sum of the array matches the wanted sum, print for (int j=0; j<11; j++) { printf("%d ",subset[j]); } printf("\n"); done = 1; } return; } for (int i=sspos; i 

Answer 2

我认为有一种方法可以在比指数时间更好的情况下生成唯一的子集。

要有效地解决子集和，您需要使用动态编程。 对于子集和，有一些伪多项式时间算法以这种方式工作。 这篇维基百科文章可能有所帮助

Answer 3

你可以尝试我的代码（我试图只给出一个psudo代码，而不是完全解决你的功课）：

 // array is all the numbers you are looking from them // length is the number of arrays // pos is the position of the slot you are going to fill // max is nomber of slots you have to fill (in your case since you are going for the 11 sets you have to set this value as 11 // sum is the sum of all the values selected until now // searchbegin is the first element you can pick from your array (I'm using this variable to only generate subarrays of the superset (array)) // target is the targetvalue you are looking for. void generate_all(int []array, int length, int pos,int max, int sum,int searchbegin,int target) { if max = pos if sum = target printselectedresults(); for i:searchbegin->length-max+pos if (sum + array[i] < target) { addtoresults(i); generate_all(array,length,pos+1,max,sum+array[i],i+1,target); removefromresults(i); } } 

有了这些信息，我认为您可以轻松地将此代码实现为目标语言并使用它。

在我的函数中，所生成的所有排列都是超集的子数组，因此不能生成两次排列，并且每个排列至少生成一次。