jjzjj

javascript - 找到在一定限制下给出最大总和的子集(子集总和)

coder 2024-07-25 原文

我有一个包含一些整数值的数组，我需要得到它们的一个子集，它给出低于给定值的最大总和。
假设我有这个数组:

[40, 138, 29, 450]

我想得到这个数组的一个子集，使总和最大化但低于用户给定的限制，比方说 250。在这种情况下，它应该返回 [139, 40, 29]。
我看了看 this问题和相关答案，并尝试使用给出的代码，但我不是很了解。不管怎样，我试过了，将最小值设置为 0，将最大值设置为给定的限制，但它一直返回我不正确的“5”，因为限制就像 300，而我数组中的数字都超过了 50。
我找不到任何可以帮助我的东西，所以我想问是否有人可以给我一些代码或伪代码来了解如何执行此操作。

最佳答案

基本上，您可以将索引处的元素添加到临时数组中，也可以不添加。然后检查索引是否达到数组的长度或者总和是否大于想要的总和，然后检查总和并将临时数组添加到结果集中，或者不。

继续，直到访问完所有索引。

function getCombinations(array, sum) {
    function add(a, b) { return a + b; }

    function fork(i, t) {
        var r = (result[0] || []).reduce(add, 0),
            s = t.reduce(add, 0);
        if (i === array.length || s > sum) {
            if (s <= sum && t.length && r <= s) {
                if (r < s) {
                    result = [];
                }
                result.push(t);
            }
            return;
        }
        fork(i + 1, t.concat([array[i]]));
        fork(i + 1, t);
    }

    var result = [];
    fork(0, []);
    return result;
}

console.log(getCombinations([40, 138, 29, 450], 250));
.as-console-wrapper { max-height: 100% !important; top: 0; }

关于javascript - 找到在一定限制下给出最大总和的子集(子集总和)，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/47891953/

javascript子集sectioncode给定algorithmsubset-sum

有关javascript - 找到在一定限制下给出最大总和的子集(子集总和)的更多相关文章

  1. ruby-on-rails - capybara ::ElementNotFound:无法找到 xpath "/html" - 2

    我正在学习http://ruby.railstutorial.org/chapters/static-pages上的RubyonRails教程并遇到以下错误StaticPagesHomepageshouldhavethecontent'SampleApp'Failure/Error:page.shouldhave_content('SampleApp')Capybara::ElementNotFound:Unabletofindxpath"/html"#(eval):2:in`text'#./spec/requests/static_pages_spec.rb:7:in`(root)'

  2. ruby - 如何找到调用当前方法的方法 - 2

    如何找到调用此方法的位置？defto_xml(options={})binding.pryoptions=options.to_hifoptions&&options.respond_to?(:to_h)serializable_hash(options).to_xml(options)end 最佳答案 键入caller。这将返回当前调用堆栈。文档:Kernel#caller.例子[0]%rspecspec10/16|===================================================62=====

  3. ruby-on-rails - 需要帮助最大化多个相似对象中的 3 个因素并适当排序 - 2

    我需要用任何语言编写一个算法，根据3个因素对数组进行排序。我以度假村为例(如Hipmunk)。假设我想去度假。我想要最便宜的地方、最好的评论和最多的景点。但是，显然我找不到在所有3个中都排名第一的方法。Example(assumingthereare20importantattractions):ResortA:$150/night...98/100infavorablereviews...18of20attractionsResortB:$99/night...85/100infavorablereviews...12of20attractionsResortC:$120/night

  4. ruby-on-rails - 使用 javascript 更改数据方法不会更改 ajax 调用用户的什么方法？ - 2

    我遇到了一个非常奇怪的问题，我很难解决。在我看来，我有一个与data-remote="true"和data-method="delete"的链接。当我单击该链接时，我可以看到对我的Rails服务器的DELETE请求。返回的JS代码会更改此链接的属性，其中包括href和data-method。再次单击此链接后，我的服务器收到了对新href的请求，但使用的是旧的data-method，即使我已将其从DELETE到POST(它仍然发送一个DELETE请求)。但是，如果我刷新页面，HTML与"new"HTML相同(随返回的JS发生变化)，但它实际上发送了正确的请求类型。这就是这个问题令我困惑的

  5. python - 帮我找到合适的 ruby​​/python 解析器生成器 - 2

    我使用的第一个解析器生成器是Parse::RecDescent，它的指南/教程很棒，但它最有用的功能是它的调试工具，特别是tracing功能(通过将$RD_TRACE设置为1来激活)。我正在寻找可以帮助您调试其规则的解析器生成器。问题是，它必须用python或ruby​​编写，并且具有详细模式/跟踪模式或非常有用的调试技术。有人知道这样的解析器生成器吗？编辑:当我说调试时，我并不是指调试python或ruby​​。我指的是调试解析器生成器，查看它在每一步都在做什么，查看它正在读取的每个字符，它试图匹配的规则。希望你明白这一点。赏金编辑:要赢得赏金，请展示一个解析器生成器框架，并说明它的

  6. ruby-on-rails - Rails 3 在一个查询中包含多个表 - 2

    我正在为锦标赛开发一个Rails应用程序。我在这个查询中使用了三个模型:classPlayertruehas_and_belongs_to_many:tournamentsclassTournament:destroyclassPlayerMatch"Player",:foreign_key=>"player_one"belongs_to:player_two,:class_name=>"Player",:foreign_key=>"player_two"在tournaments_controller的显示操作中，我调用以下查询:Tournament.where(:id=>params

  7. ruby - 404 未找到，但可以从网络浏览器正常访问 - 2

    我在这方面尝试了很多URL，在我遇到这个特定的之前，它们似乎都很好:require'rubygems'require'nokogiri'require'open-uri'doc=Nokogiri::HTML(open("http://www.moxyst.com/fashion/men-clothing/underwear.html"))putsdoc这是结果:/Users/macbookair/.rvm/rubies/ruby-2.0.0-p481/lib/ruby/2.0.0/open-uri.rb:353:in`open_http':404NotFound(OpenURI::HT

  8. ruby-on-rails - 通过 has_many 找到 Rails :through - 2

    我正在寻找一种方法来通过关联查询基于has_many中的子项的模型。我有3个模型:classConversation我需要找到参与者匹配一组ID的对话。这是我目前拥有的(不工作):Conversation.includes(:participants).where(participants:params[:participants]) 最佳答案 听起来你只是想要对话，如果是这样你可以加入。Conversation.joins(:participants).where(:users=>{:id=>params[:participant

  9. arrays - 在一行中选择数组的第一个和最后一个元素 - 2

    我的任务是从数组中选择最高和最低的数字。我想我很清楚我想做什么，但只是努力以正确的格式访问信息以满足通过标准。defhigh_and_low(numbers)array=numbers.split("").map!{|x|x.to_i}array.sort!{|a,b|ba}putsarray[0,-1]end数字可能看起来像"80917234100"，要通过，我需要输出"9234"。我正在尝试putsarray.first.last，但一直无法弄明白。 最佳答案 有Array#minmax完全满足您需要的方法:array=[80,

  10. ruby - capybara 无法通过 id 找到元素 - 2

    capybara找不到在我的cucumber测试中用它的id标记。当我save_and_open_page时，我能够看到该元素.但我无法通过has_css?找到它或find:pry(#)>page.html.scan(/notice_sent/).count=>1pry(#)>page.html.scan(/id=\"notice_sent\"/).count=>1pry(#)>page.find('#notice_sent')Capybara::ElementNotFound:Unabletofindcss"#notice_sent"from/Users/me/.gem/ruby/2

随机推荐