优化子集和实施 [英] Optimizing subset sum implementation

问题描述

我正在解决的子集和问题的一个变型中，使用下面的code。这个问题，您必须从一个更大的集（超）产生的11整数子集，并检查是否匹配特定值（endsum）。

I'm working on a solution to a variant of the subset sum problem, using the below code. The problem entails generating subsets of 11 ints from a larger set (superset) and check if it matches a specific value (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），它是缓慢和低效的，因为它产生每一个可能的排列，而不是仅仅独特的。如何优化它只能产生独特的子集？

Although this solution works for small supersets (<15) it is slow and inefficient because it generates every possible permutation instead of just the unique ones. How can I optimize it to generate only unique subsets?

编辑：完整的源$ C ​​$ c。通过大众需求增加

Complete source code added by popular demand.

推荐答案

只生成唯一子集的一种方法是添加为了从超的元素，并使用一个额外的参数置换（如 supersetPos ）以表明您身在何处的超集。这会产生有序的排列，这将是独一无二的。

One way to only generate unique subsets is to add the elements from the superset in order, and use an additional argument to permute (eg. supersetPos) to indicate where you are in the superset. This generates sorted permutations which will be unique.

修改：那据我所知正确运行在你的样品code：

EDIT: Code that AFAIK runs correctly on your sample:

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

这篇关于优化子集和实施的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！