给定数组中的子序列数量，这些子序列的总和小于或等于给定数字？（计算技术相关）

Question

我有一个大小为n的整数值数组和一个给定的数字S。

1<=n<=30

我想找到总数为S的 子序列，使得每个子序列元素之和小于S。例如：假设n=3，S=5，数组元素为{1,2,3}，则其子序列总数为7，如下所示-

{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}

但是，所需的子序列是：

{1},{2},{3},{1,2},{1,3},{2,3}

这里有一个序列 {1,2,3}，因为它的元素和 (1+2+3)=6 大于给定的值 S，所以不会被计算。其他子序列的元素和都小于给定的值 S，所以总共有 6 种可能的子序列。

我已经尝试了递归方法，但是它的时间复杂度是 2^n。请帮助我们用多项式时间解决问题。

- Enigma

---

在最坏的情况下，你可能仍需要2^n的时间。https://zh.wikipedia.org/wiki/%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98 - Petar Petrovic

@Keith，我认为这应该是一个称为0/1背包问题的特殊情况。 - Petar Petrovic

@PasserBy 我刚意识到这可能不是原始的背包问题。但是这个任务不是要找到一组零和/固定和的物品吗？（这就是子集和想要做的事情） - Petar Petrovic

如果您可以再等一周，您将在正在进行的比赛的此问题的编辑中找到一个有效的解决方案：https://www.codechef.com/MAY17/problems/CHEFCODE。那里的问题涉及产品，但思路是相同的。 - danbanica

@PetarPetrovic "你在调用子集和求解器来解决问题吗？" 不，我做的恰恰相反。我使用所谓的多项式解法来解决用户问题中的子集和问题，以此在多项式时间内解决它。你可以将任何NP完全问题归约到任何其他问题上，所以这里没有什么意外。 - n. m.

Answer 1

如果数字被限制为正数（或者严格来说是零，但我假设为正数），那么您可以使用背包问题的伪多项式算法在合理的时间内解决这个问题。它被称为伪多项式，因为它以nS时间运行。看起来像是多项式，但实际上不是，因为问题有两个复杂度参数：第一个是n，第二个是“S”的“大小”，即“S”的数字数量，称其为M。因此，该算法实际上是n 2^M。

要解决这个问题，让我们定义一个二维矩阵A。它有n行和S列。我们将说A [i] [j]是使用前i个元素并且最大和不超过j的子序列的数量。立即观察到A的右下角元素是解决方案，即A [n] [S]（是的，我们使用基于1的索引）。

现在，我们想要一个关于A [i] [j]的公式。请注意，所有使用前i个元素的子序列都包括第i个元素或不包括。不包括的子序列数量只是A [i-1] [j]。包括的子序列数量只是A [i-1] [j-v [i]]，其中v [i]只是第i个元素的值。那是因为通过包含第i个元素，我们需要保持和的余数在j-v [i]以下。因此，通过添加这两个数字，我们可以将包含和不包含第j个元素的子序列组合起来，以获得总数。因此，这导致了以下算法（注意：我对元素和i使用基于零的索引，但是对于j使用基于1的索引）：

std::vector<int> elements{1,2,3};
int S = 5;
auto N = elements.size();
std::vector<std::vector<int>> A;
A.resize(N);
for (auto& v : A) {
    v.resize(S+1);  // 1 based indexing for j/S, otherwise too annoying
}

// Number of subsequences using only first element is either 0 or 1
for (int j = 1; j != S+1; ++j) {
    A[0][j] = (elements[0] <= j);
}

for (int i = 1; i != N; ++i) {
    for (int j = 1; j != S+1; ++j) {
        A[i][j] = A[i-1][j];  // sequences that don't use ith element
        auto leftover = j - elements[i];
        if (leftover >= 0) ++A[i][j];  // sequence with only ith element, if i fits
        if (leftover >= 1) {  // sequences with i and other elements
            A[i][j] += A[i-1][leftover];
        }
    }
}

运行此程序并输出 A[N-1][S]，即可得到所需的6。如果该程序运行速度不够快，您可以通过使用单个向量而不是向量数组来显着提高性能（并且您可以通过不浪费列来进行1索引来节省一些空间/性能，就像我所做的那样）。

- Nir Friedman

Answer 2

是的。这个问题可以在伪多项式时间内解决。

让我重新定义问题陈述为“计算子集中SUM <= K的数量”。

下面给出了一个解决方案，其时间复杂度为O（N * K），

其中N是元素的数量，K是目标值。

int countSubsets (int set[], int K) {
    int dp[N][K];

    //1. Iterate through all the elements in the set.
    for (int i = 0; i < N; i++) {
        dp[i][set[i]] = 1;

        if (i == 0) continue;

        //2. Include the count of subsets that doesn't include the element set[i]
        for (int k = 1; k < K; k++) {
            dp[i][k] += dp[i-1][k];
        }

        //3. Now count subsets that includes element set[i]
        for (int k = 0; k < K; k++) {
            if (k + set[i] >= K) {
                break;
            }
            dp[i][k+set[i]] += dp[i-1][k];
        }
    }
    //4. Return the sum of the last row of the dp table.
    int count = 0;
    for (int k = 0; k < K; k++) {
        count += dp[N-1][k];
    }
    // here -1 is to remove the empty subset
    return count - 1;
}       

- XOR

---

嗯...代码无法编译，因为在//3.处缺少一个括号。 - Passer By

此外，这不是多项式时间，而是伪多项式时间，实际上是指数级的。 - Passer By

这个解决方案的时间复杂度为O(N*K)。在K的合理取值范围内，性能将非常出色。无论如何，它都比普通递归算法更高效。 - XOR

首先，它不是严格比暴力搜索更快。在一个复杂度参数方面表现更好，但在另一个方面表现更差。其次，你的代码不是有效的C++代码。可变长度数组不是C++的一部分。 - Nir Friedman