草庐IT

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

coder 2024-02-24 原文

我有一个大小为 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/

给定ampcodesectionstrongc++arraysalgorithmsubsequence

有关c++ - 计算给定数组的子序列数，使得它们的总和小于或等于给定数？的更多相关文章

  1. ruby-on-rails - 在 Ruby 中循环遍历多个数组 - 2

    我有多个ActiveRecord子类Item的实例数组，我需要根据最早的事件循环打印。在这种情况下，我需要打印付款和维护日期，如下所示:ItemAmaintenancerequiredin5daysItemBpaymentrequiredin6daysItemApaymentrequiredin7daysItemBmaintenancerequiredin8days我目前有两个查询，用于查找maintenance和payment项目(非排他性查询)，并输出如下内容:paymentrequiredin...maintenancerequiredin...有什么方法可以改善上述(丑陋的)代

  2. ruby - 什么是填充的 Base64 编码字符串以及如何在 ruby​​ 中生成它们？ - 2

    我正在使用的第三方API的文档状态:"[O]urAPIonlyacceptspaddedBase64encodedstrings."什么是“填充的Base64编码字符串”以及如何在Ruby中生成它们。下面的代码是我第一次尝试创建转换为Base64的JSON格式数据。xa=Base64.encode64(a.to_json) 最佳答案 他们说的padding其实就是Base64本身的一部分。它是末尾的“=”和“==”。Base64将3个字节的数据包编码为4个编码字符。所以如果你的输入数据有长度n和n%3=1=>"=="末尾用于填充n%

  3. ruby - 多次弹出/移动 ruby​​ 数组 - 2

    我的代码目前看起来像这样numbers=[1,2,3,4,5]defpop_threepop=[]3.times{pop有没有办法在一行中完成pop_three方法中的内容？我基本上想做类似numbers.slice(0,3)的事情，但要删除切片中的数组项。嗯...嗯，我想我刚刚意识到我可以试试slice! 最佳答案 是numbers.pop(3)或者numbers.shift(3)如果你想要另一边。 关于ruby-多次弹出/移动ruby​​数组，我们在StackOverflow上找到一

  4. ruby - 将数组的内容转换为 int - 2

    我需要读入一个包含数字列表的文件。此代码读取文件并将其放入二维数组中。现在我需要获取数组中所有数字的平均值，但我需要将数组的内容更改为int。有什么想法可以将to_i方法放在哪里吗？ClassTerraindefinitializefile_name@input=IO.readlines(file_name)#readinfile@size=@input[0].to_i@land=[@size]x=1whilex 最佳答案 只需将数组映射为整数:@land边注如果你想得到一条线的平均值，你可以这样做:values=@input[x]

  5. ruby-on-rails - 如何优雅地重启 thin + nginx？ - 2

    我的瘦服务器配置了nginx，我的ROR应用程序正在它们上运行。在我发布代码更新时运行thinrestart会给我的应用程序带来一些停机时间。我试图弄清楚如何优雅地重启正在运行的Thin实例，但找不到好的解决方案。有没有人能做到这一点？ 最佳答案 #Restartjustthethinserverdescribedbythatconfigsudothin-C/etc/thin/mysite.ymlrestartNginx将继续运行并代理请求。如果您将Nginx设置为使用多个上游服务器，例如server{listen80;server

  6. ruby - 通过 erb 模板输出 ruby​​ 数组 - 2

    我正在使用puppet为ruby​​程序提供一组常量。我需要提供一组主机名，我的程序将对其进行迭代。在我之前使用的bash脚本中，我只是将它作为一个puppet变量hosts=>"host1,host2"我将其提供给bash脚本作为HOSTS=显然这对ruby​​不太适用——我需要它的格式hosts=["host1","host2"]自从phosts和putsmy_array.inspect提供输出["host1","host2"]我希望使用其中之一。不幸的是，我终其一生都无法弄清楚如何让它发挥作用。我尝试了以下各项:我发现某处他们指出我需要在函数调用前放置“function_”……这

  7. ruby - 检查数组是否在增加 - 2

    这个问题在这里已经有了答案:Checktoseeifanarrayisalreadysorted?(8个答案)关闭9年前。我只是想知道是否有办法检查数组是否在增加？这是我的解决方案，但我正在寻找更漂亮的方法:n=-1@arr.flatten.each{|e|returnfalseife

  8. ruby-on-rails - 使用一系列等级计算字母等级 - 2

    这里是Ruby新手。完成一些练习后碰壁了。练习:计算一系列成绩的字母等级创建一个方法get_grade来接受测试分数数组。数组中的每个分数应介于0和100之间，其中100是最大分数。计算平均分并将字母等级作为字符串返回，即“A”、“B”、“C”、“D”、“E”或“F”。我一直返回错误:avg.rb:1:syntaxerror,unexpectedtLBRACK,expecting')'defget_grade([100,90,80])^avg.rb:1:syntaxerror,unexpected')',expecting$end这是我目前所拥有的。我想坚持使用下面的方法或.join，

  9. ruby - 如果指定键的值在数组中相同，如何合并哈希 - 2

    我有一个这样的哈希数组:[{:foo=>2,:date=>Sat,01Sep2014},{:foo2=>2,:date=>Sat,02Sep2014},{:foo3=>3,:date=>Sat,01Sep2014},{:foo4=>4,:date=>Sat,03Sep2014},{:foo5=>5,:date=>Sat,02Sep2014}]如果:date相同，我想合并哈希值。我对上面数组的期望是:[{:foo=>2,:foo3=>3,:date=>Sat,01Sep2014},{:foo2=>2,:foo5=>5:date=>Sat,02Sep2014},{:foo4=>4,:dat

  10. ruby - 在 Ruby 中用键盘诅咒数组浏览 - 2

    我正在尝试在Ruby中制作一个cli应用程序，它接受一个给定的数组，然后将其显示为一个列表，我可以使用箭头键浏览它。我觉得我已经在Ruby中看到一个库已经这样做了，但我记不起它的名字了。我正在尝试对soundcloud2000中的代码进行逆向工程做类似的事情，但他的代码与SoundcloudAPI的使用紧密耦合。我知道cursesgem，我正在考虑更抽象的东西。广告有没有人见过可以做到这一点的库或一些概念证明的Ruby代码可以做到这一点？ 最佳答案 我不知道这是否是您正在寻找的，但也许您可以使用我的想法。由于我没有关于您要完成的工作

随机推荐