如何适配高效回溯子集和算法以处理含正负整数的超大输入集

问题描述 #

我需要处理规模在3到1000万之间、包含正负整数的超大集合的子集和问题，之前尝试后觉得几乎无法实现。后来找到一个高效的递归回溯算法，重新有了思路，但很难调整它以支持正负整数——目前只知道要把代码中的unsigned int改为int，不清楚后续该怎么操作。

原代码 #

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

short* flag;
int N, K, correspond = 0;
unsigned int* check, X = 0;
clock_t t1, t2;

void init() {
    int i, j;

    printf("N=");
    scanf_s("%d", &N);

    check = malloc(sizeof(unsigned int) * N);
    if (check == NULL) {
        perror("Out of memory");
        exit(-1);
    }

    srand((unsigned)time(NULL));
    printf("\n///check list///\n");
    for (i = 0; i < N; i++) {
        check[i] = rand() % 1000000 + 1;
        printf("%u\n ", check[i]);
    }
    printf("\n");

    K = rand() % N;

    flag = malloc(sizeof(short) * N);
    for (i = 0; i < N; i++)flag[i] = 0; 
    i = 0;
    while (i <= K) {
        j = rand() % N;
        if (flag[j] == 0) {
            flag[j] = 1;
            X = X + check[j];
            i++;
        }
    }
    printf("\nX=%u\n", X);
}

void swap(int j, int k) {
    unsigned int tmp;

    tmp = check[j];
    check[j] = check[k];
    check[k] = tmp;
}

int partition(int left, int right) {
    int j = left, k = right;
    unsigned int v;

    v = check[(left + right) / 2];
    do {
        while (check[j] > v) j++;
        while (v > check[k]) k--;
        swap(j, k);
    } while (check[j] != check[k]);

    return j;
}

void quicksort(int left, int right) {
    int j;

    if (left < right) {
        j = partition(left, right);
        quicksort(left, j - 1);
        quicksort(j + 1, right);
    }
}

void func(unsigned int sum, int i) {
    int j, k, t = 0;

    if (sum == X) {
        correspond = 1;
        t2 = clock();
        double record = (double)(t2 - t1) / CLOCKS_PER_SEC;

        printf("\nAnswer : ");
        for (k = 0; k < N; k++) {
            if (flag[k] == 1) {
                if (t == 0) t = 1;
                else if (t == 1) printf("+");
                printf("%u", check[k]);
            }
        }
        printf("\n\nThinking time : %f sec . \n", record);
        if (record <= 60) printf("Triumph!\n");
        else printf("Failure...\n");
        return;
    }
    else if (sum < X) {
        for (j = i + 1; (j <= N) && (correspond == 0); j++) {
            flag[j] = 1;
            func(sum + check[j], j);
        }
    }
    flag[i] = 0;
    return;
}

int main() {
    int i;

    init();
    t1 = clock();
    for (i = 0; i < N; i++)flag[i] = 0;
    quicksort(0, N);
    func(0, 0);

    return 0;
}

补充说明 #

• 该算法名为Amortized O(n) algorithm based on Recursive Backtracking，我不太理解为何称其为"Amortized"——这个术语通常指将输入数组划分为多个子集，再对每个子集使用多项式时间算法。
• 我已尝试修复用户指出的问题，希望得到反馈。

内容的提问来源于stack exchange，提问作者Talon Van Vuuren