c - 算法 : To determine whether a given set has two subsets which are disjoint such that sum of elements in both subsets is same?

Question

这是我写的代码:-

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

int ctr = 0;

void partition(int arr[], int n) {
    int i, j, k = 0, r, in = 0, te, flag = 0;
    int *sum;
    sum = (int*)malloc(sizeof(int) * pow(2, n));
    for (i = 0; i < pow(2, n); i++) {
        printf("{");
        for (j = 0; j < n; j++) {
            if (i & (1 << j)) {
                printf("%d ", arr[j]);
                sum[k] = sum[k] + arr[j];
            }
        }
        k++;
        printf("}");
        printf("\n");
    }
    printf("\n \n");

    int *temp;
    for (k = 0; k < pow(2, n) - 1; k++) {
        in = 0;
        temp = (int*)malloc(sizeof(int));
        for (r = k + 1; r < pow(2, n); r++) {
            if (sum[k] == sum[r]) {
                printf("\n Printing solution for sum %d", sum[k]);
                for (i = 0; i < pow(2, n); i++) {
                    if (i == k || i == r) {
                        printf("{");
                        for (j = 0; j < n; j++) {
                            if (i & 1 << j) {
                                for (te = 0; te < in; te++) { //Disjointness
                                    if (temp[te] == arr[j])
                                        flag = 1;
                                }
                                if (flag == 1)
                                    break;
                                temp[in++] = arr[j];
                                temp = (int*)realloc(temp, sizeof(int));
                                printf("%d ", arr[j]);
                            }
                        }
                        printf("}");
                        printf("\n");
                    }
                }
                break;          
            }
        }
        free(temp);
    }
}

void main() {
    int *arr, n, i;
    printf("\n Enter the number of elements in the set \n");
    scanf("%d", &n);
    arr = (int*)malloc(sizeof(int) * n);
    printf("\n Enter the set elements \n");
    for (i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }
    partition(arr, n);
}

它非常适合输入 {1,2,3}。对于 {1,2,3,4}，它也给出了正确的输出。

对于{1,2,3,4}，输出是:

Printing solution for sum 3{1 2 }
{3 }

 Printing solution for sum 4{1 3 }
{4 }

 Printing solution for sum 5{2 3 }
{1 4 }

 Printing solution for sum 6{1 2 3 }
{}

 Printing solution for sum 7{}
{}

但是如果输入是{1,5,11,5}，输出是:

 Printing solution for sum 5{5 }
{}

 Printing solution for sum 6{}
{}

 Printing solution for sum 11{}
{}

 Printing solution for sum 16{}
{}

 Printing solution for sum 17{}
{}

因为 {1,5,5} 和 {11} 是一个解决方案，在这种情况下，预期输出应该是 Printing Solution for sum 11 {1,5,5} 和 {11} 但它没有显示。

问题是什么，我该如何解决？

Answer 1

你的算法太复杂了。您从正确的路径开始，计算该集合所有子集的总和，但您没有正确计算所有可能的不相交子集来尝试找到一个总和相同的子集。

这里有一个更简单的方法:

• 枚举所有子集
• 对于每个子集，计算总和并将具有子集签名及其总和的结构存储到数组中。
• 按总和的值对数组排序
• 迭代排序后的数组:
• 对于每个元素，迭代具有相同总和的后续元素，如果其中一个元素具有不相交的子集签名，则您有一个匹配项，打印它。
• 空间复杂度为O(2^N)，时间复杂度为O(2^N+1 )，这是非常糟糕的，但对于小集合来说是可以管理的。

修改后的版本:

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

struct s { int sig, sum; };

int compare(const void *p1, const void *p2) {
    int sum1 = ((const struct s*)p1)->sum;
    int sum2 = ((const struct s*)p2)->sum;
    return (sum1 > sum2) - (sum1 < sum2);
}

void print_set(int arr[], size_t sig) {
    printf("{");
    while (sig) {
        if (sig & 1)
            printf(" %d", *arr);
        arr++;
        sig >>= 1;
    }
    printf(" } ");
}

void partition(int arr[], int n) {
    size_t i, j, count = 1ULL << n;
    struct s *array = calloc(sizeof(*array), count);
    int b, sum;

    if (array != NULL) {
        for (i = 1; i < count; i++) {
            sum = 0;
            for (b = 0; b < n; b++) {
                if (i & (1ULL << b))
                    sum += arr[b];
            }
            array[i].sig = i;
            array[i].sum = sum;
        }
        qsort(array, count, sizeof(*array), compare);
        for (i = 0; i < count; i++) {
            for (j = i + 1; j < count && array[i].sum == array[j].sum; j++) {
                if ((array[i].sig & array[j].sig) == 0) {
                    printf("solution with sum=%d: ", array[i].sum);
                    print_set(arr, array[i].sig);
                    print_set(arr, array[j].sig);
                    printf("\n");
                }
            }
        }
        free(array);
    }
}

int main() {
    int *arr, n, i;
    printf("Enter the number of elements in the set: ");
    if (scanf("%d", &n) == 1) {
        arr = (int*)malloc(sizeof(int) * n);
        if (arr != NULL) {
            printf("Enter the set elements: ");
            for (i = 0; i < n; i++) {
                if (scanf("%d", &arr[i]) != 1)
                    return 1;
            }
            partition(arr, n);
            free(arr);
        }
    }
    return 0;
}

输出:

Enter the number of elements in the set: 3
Enter the set elements:  1 2 3
solution with sum=3: { 3 } { 1 2 } 

Enter the number of elements in the set: 4
Enter the set elements: 1 2 3 4
solution with sum=3: { 1 2 } { 3 }
solution with sum=4: { 4 } { 1 3 }
solution with sum=5: { 2 3 } { 1 4 }

Enter the number of elements in the set: 4
Enter the set elements: 1 5 11 5
solution with sum=5: { 5 } { 5 }
solution with sum=11: { 11 } { 1 5 5 }