在一个集合中找到一组数字，使它们的和等于另一个集合中的某个数字。

Question

我正在制作一个游戏，有这样一种情况：我有一组数字列表，比如[7, 4, 9, 1, 15, 2]（用A表示），还有另一组数字列表，比如[11, 18, 14, 8, 3]（用B表示）。目标是找到A中所有加起来等于B中数字的组合。例如:

• 1 + 2 = 3
• 1 + 7 = 8
• 2 + 9 = 11
• 4 + 7 = 11
• 1 + 2 + 4 + 7 = 14
• 1 + 2 + 15 = 18
• 2 + 7 + 9 = 18

对于像这样的小列表，直接使用暴力法即可找出所有组合，但我可能会遇到数千个到数万个这些数字，并且在应用程序的生命周期内将重复使用此例程。是否有一种优雅的算法在合理的时间内完成此任务并具有100％的覆盖率？如果失败，是否可以找到任何类型的良好启发式算法，在合理的时间内给我提供“足够好”的组合集？

我需要的是以伪代码形式或以任何流行的易读编程语言（请注意“和”这个词……;)）描述的算法，甚至只需要英文描述也行。

---

编辑补充:

提供了许多有用的信息。 谢谢！ 现在总结如下:

• 问题是NP完全问题，因此除了暴力搜索之外，没有任何方法可以在合理的时间内获得100％准确性。

这个问题可以看作是子集和问题或背包问题的变体。这两个问题都有众所周知的启发式方法，可适用于此问题。

继续提出想法！再次感谢！

- JUST MY correct OPINION

---

如果存在某些可以利用的限制条件，那么可以使用一些启发式方法。例如，数组A和B的大小和/或成员是否恒定？或者你可能会遇到的数字范围是有限的吗？ - tathagata

@tathagata：数字永远不会超过30或低于1。这将是一个限制条件。 - JUST MY correct OPINION

如果是这样，问题并不难。您可以创建一个列表，其中包含数字1到30的所有组合以及每个组合所需的数字。然后，您可以创建一个包含列表“A”中出现的所有数字的列表。最后，您可以检查每个组合是否需要的数字都在“出现在A列表中”。 - rudi-moore

@Just... B中的数字是否也在1到30之间？如果是，那么问题是可处理的，需要相当大但合理的空间。 - Il-Bhima

@Il-Bhima：是的。所有涉及到这样比较的数字将会在1-30之间。空间大多不是问题。 - JUST MY correct OPINION

Answer 1

这个问题是NP-Complete的... 这是子集和问题的某种变体，已知其为NP-Complete问题（实际上，子集和问题比您的问题更容易）。

欲了解更多信息，请阅读： http://en.wikipedia.org/wiki/Subset_sum_problem

- Protostome

---

我有一种隐约的感觉，这个问题可能是NP难问题或者更糟。有什么启发式算法可以应用吗？ - JUST MY correct OPINION

当然可以。首先，在维基百科的文章中有一个近似算法，请查看是否符合您的需求。其次，您可以应用分支定界方法（或alpha-beta剪枝）。如果您的列表中最大数有上限，您还可以应用一些启发式方法，例如编制一个关于在B中将数字t加起来得到所有可能结果的列表。（仅当t、B相对较小而A很大时才值得尝试...） - Protostome

Answer 2

如评论中所述，由于数字仅在1到30之间，因此该问题具有快速解决方案。我在C语言中进行了测试，在您给出的示例中，它只需要毫秒级别的时间，并且将很好地扩展。复杂度为O（n + k），其中n是列表A的长度，k是列表B的长度，但具有很高的常数因子（有28,598种可能性可以得到1到30的总和）。

#define WIDTH 30000
#define MAXNUMBER 30

int create_combination(unsigned char comb[WIDTH][MAXNUMBER+1], 
                       int n, 
                       unsigned char i, 
                       unsigned char len, 
                       unsigned char min, 
                       unsigned char sum) {
    unsigned char j;

    if (len == 1) {
        if (n+1>=WIDTH) {
            printf("not enough space!\n");
            exit(-1);
        }
        comb[n][i] = sum;
        for (j=0; j<=i; j++)
            comb[n+1][j] = comb[n][j];
        n++;
        return n;
    }

    for (j=min; j<=sum/len; j++) {
        comb[n][i] = j;
        n = create_combination(comb, n, i+1, len-1, j, sum-j);
    }

    return n;
}

---

int main(void)
{
    unsigned char A[6] = { 7, 4, 9, 1, 15, 2 };
    unsigned char B[5] = { 11, 18, 14, 8, 3 };

    unsigned char combinations[WIDTH][MAXNUMBER+1];
    unsigned char needed[WIDTH][MAXNUMBER];
    unsigned char numbers[MAXNUMBER];
    unsigned char sums[MAXNUMBER];
    unsigned char i, j, k;
    int n=0, m;

    memset(combinations, 0, sizeof combinations);
    memset(needed, 0, sizeof needed);
    memset(numbers, 0, sizeof numbers);
    memset(sums, 0, sizeof sums);

    // create array with all possible combinations
    // combinations[n][0] stores the sum
    for (i=2; i<=MAXNUMBER; i++) {
        for (j=2; j<=i; j++) {
            for (k=1; k<=MAXNUMBER; k++)
                combinations[n][k] = 0;
            combinations[n][0] = i;
            n = create_combination(combinations, n, 1, j, 1, i);
        }
    }

    // count quantity of any summands in each combination
    for (m=0; m<n; m++)
        for (i=1; i<=MAXNUMBER && combinations[m][i] != 0; i++)
            needed[m][combinations[m][i]-1]++;

    // count quantity of any number in A
    for (m=0; m<6; m++)
        if (numbers[A[m]-1] < MAXNUMBER)
            numbers[A[m]-1]++;

    // collect possible sums from B
    for (m=0; m<5; m++)
        sums[B[m]-1] = 1;

    for (m=0; m<n; m++) {
        // check if sum is in B
        if (sums[combinations[m][0]-1] == 0)
            continue;

        // check if enough summands from current combination are in A
        for (i=0; i<MAXNUMBER; i++) {
            if (numbers[i] < needed[m][i])
                break;
        }

        if (i<MAXNUMBER)
            continue;

        // output result
        for (j=1; j<=MAXNUMBER && combinations[m][j] != 0; j++) {
            printf(" %s %d", j>1 ? "+" : "", combinations[m][j]);
        }
        printf(" = %d\n", combinations[m][0]);
    }

    return 0;
}

---

1 + 2 = 3
1 + 7 = 8
2 + 9 = 11
4 + 7 = 11
1 + 4 + 9 = 14
1 + 2 + 4 + 7 = 14
1 + 2 + 15 = 18
2 + 7 + 9 = 18

- rudi-moore

Answer 3

听起来像是背包问题（参见http://en.wikipedia.org/wiki/Knapsack_problem）。在该页面上，他们还解释了这个问题通常是NP完全的。

我认为这意味着如果你想找到所有有效的组合，你只需要花费很多时间。

- Patrick

---

那就是为什么我也问了一下能够在合理时间内给我“足够好”的结果的启发式方法。 - JUST MY correct OPINION

Answer 4

这是子集和问题的一个小泛化。一般来说，它是NP完全问题，但只要所有数字都是整数且B中的最大数字相对较小，我在维基百科文章中提到的伪多项式解决方案应该能解决问题。

- svick