一道算法题求教

Question

在效率尽可能高的情况下解答：
在给定一个由n个整数构成的集合S和另一个整数x时，判断出S中是否存在有任意个其和等于x的元素？

Answer 1

通过维基百科和stackoverflow 知道这是subset problem

采用动态规划进行求解：
1. 设集合x的最小和以及最大和分别是min，max，设一个二维数组 m[n][max-min]
m[i][s] = 1表示找到了x[1...i]的一个子集和等于s

因此初试条件：m[1][x1] = 1
递推关系：
m[2][x] = 1 if m[1][x-x2] = 1, 否则 m[2][x] = m[1][x]

Answer 2

任意个其和？应该说有多少种方案吧！典型组合数学，去翻翻书就知道了.

Answer 3

这个题目是01背包的变种吧，楼主可以先去学习下01背包。事实上我们可以这么做我们设布尔变量fi为1~i个数中是否存在和为x的任意元素，那么我们可以得到递推表达式f[i][j] = (f[i - 1][j - arr[i]] | f[i - 1][j]);其中f[i - 1][j - arr[i]]意思是选这个元素可不可能实现。f[i - 1][j]的意思就是不选这个元素可不可以实现。所以最后我们可以得到这样的一个程序：

#include <iostream>

int n, x, arr[100];
bool f[100][100000];

int main(int argc, char const *argv[]) {
    scanf("%d %d", &n, &x);
    f[0][0] = true;
    for (int i = 1; i <= n; ++i)
        f[i][0] = true;
    for (int i = 1; i <= n; ++i) 
        scanf("%d", &arr[i]);

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= x; ++j) {
            if (j >= arr[i]) 
                f[i][j] = (f[i - 1][j - arr[i]] | f[i - 1][j]);
            else f[i][j] = f[i - 1][j]; //如果当前当前元素比x大那么我们不选结果就是不选的那个
        }
    }

    if (f[n][x]) printf("YES\n");
    else printf("NO\n");

    return 0;
}

最后时间复杂度 O(n * x)
当然如果你看懂上面的步骤的话那么你还可以对空间复杂度进行优化，优化原理如果感兴趣可以私信我或自己研究。
代码如下：

#include <iostream>

int n, x, arr[100];
bool f[100000];

int main(int argc, char const *argv[]) {
    scanf("%d %d", &n, &x);
    f[0] = true;
    for (int i = 1; i <= n; ++i) 
        scanf("%d", &arr[i]);

    for (int i = 1; i <= n; ++i) {
        for (int j = x; j >= 1; --j) {
            if (j >= arr[i]) 
                f[j] = (f[j - arr[i]] | f[j]);
            else f[j] = f[j];
        }
    }

    if (f[x]) printf("YES\n");
    else printf("NO\n");

    return 0;
}

这样空间复杂度就变为了 O(x)。
以上。