优化子集求和实现

Question

我正在使用下面的代码解决子集求和问题的一个变体。这个问题需要从一个更大的集合（超集）中生成11个整数的子集，并检查它是否与特定值（endsum）相匹配。

#include <stdio.h> 
#include <stdlib.h> 
#include <assert.h> 

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）来指示您在超集中的位置。这产生排序的排列，这将是唯一的。

编辑：代码，据我所知正确运行在您的样本：

#include <stdio.h> 

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<supersetsize; i++) { 
     subset[pos] = superset[i]; 
     permute(subset,pos+1,i+1); 
     if (done) { //when a correct solution has been found, stop recursion 
      return; 
     } 
    } 

} 
int main() { 
    int subset[11] = {0}; 
    permute(subset, 0, 0); 
} 

Answer 2

我不认为有一种方法可以产生比指数时间更独特的子集。

为了有效解决子集总和，您希望使用动态编程。有些子集和的伪多项式时间算法可以这样工作。这Wikipedia article可能会有所帮助。

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

与所有这些信息，我认为你可以很容易地实现此代码的目标语言和用它。

在我的函数中，生成的所有排列都是超集的子排列，所以不会产生两次排列，而且每个排列都至少产生一次。