我有一个大小为 n
的整数值数组和一个给定的数字 S
。
1<=n<=30
我想找到子序列的总数,使得每个子序列元素的总和小于S
。
例如:让n=3
,S=5
和数组的元素为{1,2,3}
那么它的总子序列是 7
as-
{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>S
。其他被采用是因为对于其他子序列元素总和小于S
。
因此,可能的子序列总数为 6
。
所以我的答案是计数,即6
。
我试过递归方法,但它的时间复杂度是2^n
。
请帮助我们在多项式时间内完成。
最佳答案
如果数字被限制为正数(或者,从技术上讲,为零,但我假设为正数),您可以在合理的时间内(可能)解决这个问题,使用伪多项式算法来解决背包问题。它被称为伪多项式是因为它在 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 个元素的子序列以获得总数。所以这导致我们使用以下算法(注意:我对元素和 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。如果这个程序运行得不够快,你可以通过使用单个 vector 而不是 vector 的 vector 来显着提高性能(并且你可以通过不浪费列来节省一些空间/性能,就像我所做的那样,为了 1-index ).
关于c++ - 计算给定数组的子序列数,使得它们的总和小于或等于给定数?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/43864222/