计算给定数组的子序列的数量，使它们的总和小于或等于给定的数量？

Question

我有一个大小n为整数值的数组和一个给定的 number 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}

that is{1,2,3}不被采用，因为它的元素总和(1+2+3)=6大于Sthat is 6>S。之所以采用其他，是因为，对于其他子序列，元素总和小于S。因此，可能的子序列总数为6。所以我的答案是计数，即6。

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

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元素的所有子序列要么包含该ith元素，要么不包含该元素。不存在的子序列的数量仅为A[i-1][j]。执行此操作的子序列的数量为A[i-1][j-v[i]]，其中v[i]为第 i 个元素的值。这是因为通过包含第 i 个元素，我们需要将总和的余数保留在下面j-v[i]。因此，通过将这两个数字相加，我们可以将包含和不包含第 j 个元素的子序列组合起来以获得总数。因此，这导致我们得出以下算法（注意：我对元素 和 使用基于 0 的索引i，但对 使用基于 1 的索引j）：

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 索引来节省一点空间/性能，就像我所做的那样） ）。