優化子集求和實現

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

與所有這些信息，我認爲你可以很容易地實現此代碼的目標語言和用它。

在我的函數中，生成的所有排列都是超集的子排列，所以不會產生兩次排列，而且每個排列都至少產生一次。