计算给定数组的子序列数，使其和小于或等于给定数？

Question

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

1<=n<=30

我想找到子序列的总数，使得每个子序列的元素总和小于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，即6

我尝试过递归方法，但它的时间复杂度是2^n。请帮助我们在多项式时间内完成它。




Answer 1

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

让我将问题陈述重新定义为“计算具有和的子集的数量”

下面给出的是一个在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;
}       

Answer 2

匿名用户

你可以在合理的时间内（可能）使用背包问题的伪多项式算法解决这个问题，如果数字被限制为正数（或者，从技术上讲，零，但我将假设为正数）。它被称为伪多项式，因为它在 nS 时间内运行。这看起来是多项式的。但事实并非如此，因为问题有两个复杂度参数：第一个是n，第二个是S的“大小”，即S中的位数，称之为M。所以这个算法实际上是n 2^M。

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

现在，我们需要一个＜code＞a[i][j]的公式。请注意，使用第一个i元素的所有子序列要么包括第i个，要么不包括。不存在的子序列数仅为A[i-1][j]。do的子序列的数目正好是A[i-1][j-v[i]]，其中v[i]正好是第i个元素的值。这是因为通过包含第i个元素，我们需要将和的剩余部分保持在j-v[i]以下。因此，通过将这两个数字相加，我们可以组合包含和不包含第j个元素的子序列，得到总数。因此，我们得出了以下算法（注意：我对元素和＜code＞I＜/code＞使用基于零的索引，但对＜code＞j＜/code＞使用基于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。如果此程序运行速度不够快，则可以通过使用单个向量而不是向量向量来显着提高性能（并且您可以通过不浪费列来节省一列来节省一些空间/性能，就像我所做的那样）。