草庐IT

php - 需要从多组列表中获得最佳总和组合的算法(逻辑)

coder 2024-05-04 原文

我有多组数据，比如

第 1 组 2,3,5,10,15
第 2 组 4,6,23,15,12
第 3 组 23,34,12,1,5

我需要这 3 组的最佳总和(例如总和(g1+g2+g3)<>

第一个 (g1) 5 + (g2) 15 + (g3) + 5 = 25(最佳组合)

现在，对于下一组组合，无需使用每个对应组的上述值

第 1 组 2,3,5,10,15
第 2 组 4,6,23,15,12
第 3 组 23,34,12,1,5

第二 (g1) 2 + (g2) 23 = 25(最佳组合)

组1 2,3,5,10,15
第 2 组 4,6,23,15,12
第 3 组 23,34,12,1,5

第三 (g1) 15 + (g2) 6 + (g3) + 1 = 22(最佳组合)

我希望这可能有点复杂。但我可能会得到更好的解决方案。

谢谢

最佳答案

是NP-Hard问题。

从sub-set sum开始减少
子集求和问题:给定一个多重集S和一个数字k:当且仅当存在子集时返回真S 的 >S'，其总和恰好为 k。

减少:
给定(S,k)形式的子集和问题实例，创建(G1,G2,...,Gn)形式的该问题实例,k) 其中 Gi 是一个单例组，元素 i 来自 S，k是我们要找的数字。

证明:
子集和 -> 这个问题:假设有一个子集 S'={si_1,si_2,...,si_m} 使得 si_1 + si_2 + ... + si_m = k，然后从每个组中选择一个元素:Gi_1, Gi_2, ... , Gi_m，它们总和为 k，因为每个Gi 只包含元素 si。
本题->子集和:同样的思路，假设有一组单例组，总和为k，我们可以找出其中的哪些元素S 我们需要在 S 中获得所需的子集和。

结论:
这个问题是NP-Hard的，没有已知的多项式解。由于您正在寻找的是 NP-Hard 问题的优化问题，因此您的优化问题也是 NP-Hard 问题。因此，获得最佳解决方案的最佳机会可能是指数解决方案，例如蛮力:只需检查所有可能性，然后返回最佳匹配。

注意:

  • 从示例 2 来看，您似乎不需要从每个元素中选择一个元素 组，但如果不是，则从每个组中最多选择一个元素 情况 - 这个问题仍然是 NP-Hard，但减少了 用力一点。
  • 我对维基百科的回答中的所有链接都在这里供 future 的读者使用，因为维基百科今天已下线。如果您有兴趣，可以在 google 上搜索这些术语并查看缓存页面。

编辑:指数解示例[伪代码]:

请注意它没有经过测试，但它背后的想法应该可行:只需检查第一组的所有可能性，然后递归 findBest() 少一组，所以最后 - 你耗尽所有可能的解决方案，并从中返回最好的解决方案。

findBest(groups, k):
  if (k < 0): return infinity //stop condition 1
  if (group is empty) return k //stop condition 2
  group <- groups.getFirst()
  min <- infinity
  best <- []
  for each element in group:
     (solValue,minResult) <- findBest(groups-group, k - element) //recursively check for solution, with decreasing number of groups, and modify k
     if (solValue < min):
        min <- solValue
        best <- minResult
        best.append((group,element)) //append the element we added to the solution
  //it is also possible to take no element from this group:
  (solValue,minResult) <- findBest(groups-grou, k - element)
  if (solValue < min):
     min <- solValue
     best <- minResult
  return (minResult,solValue)

关于php - 需要从多组列表中获得最佳总和组合的算法(逻辑)，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/8906341/

php需要codestrongdelalgorithmlogicsumcombinations

有关php - 需要从多组列表中获得最佳总和组合的算法(逻辑)的更多相关文章

  1. ruby-on-rails - 使用 Ruby on Rails 进行自动化测试 - 最佳实践 - 2

    很好奇，就使用ruby​​onrails自动化单元测试而言，你们正在做什么？您是否创建了一个脚本来在cron中运行rake作业并将结果邮寄给您？git中的预提交Hook？只是手动调用？我完全理解测试，但想知道在错误发生之前捕获错误的最佳实践是什么。让我们理所当然地认为测试本身是完美无缺的，并且可以正常工作。下一步是什么以确保他们在正确的时间将可能有害的结果传达给您？ 最佳答案 不确定您到底想听什么，但是有几个级别的自动代码库控制:在处理某项功能时，您可以使用类似autotest的内容获得关于哪些有效，哪些无效的即时反馈。要确保您的提

  2. ruby - 我需要将 Bundler 本身添加到 Gemfile 中吗？ - 2

    当我使用Bundler时，是否需要在我的Gemfile中将其列为依赖项？毕竟，我的代码中有些地方需要它。例如，当我进行Bundler设置时:require"bundler/setup" 最佳答案 没有。您可以尝试，但首先您必须用鞋带将自己抬离地面。 关于ruby-我需要将Bundler本身添加到Gemfile中吗？，我们在StackOverflow上找到一个类似的问题： https://stackoverflow.com/questions/4758609/

  3. ruby - 解析 RDFa、微数据等的最佳方式是什么，使用统一的模式/词汇(例如 schema.org)存储和显示信息 - 2

    我主要使用Ruby来执行此操作，但到目前为止我的攻击计划如下:使用gemsrdf、rdf-rdfa和rdf-microdata或mida来解析给定任何URI的数据。我认为最好映射到像schema.org这样的统一模式，例如使用这个yaml文件，它试图描述数据词汇表和opengraph到schema.org之间的转换:#SchemaXtoschema.orgconversion#data-vocabularyDV:name:namestreet-address:streetAddressregion:addressRegionlocality:addressLocalityphoto:i

  4. ruby - RVM 使用列表[0] - 2

    是否有类似“RVMuse1”或“RVMuselist[0]”之类的内容而不是键入整个版本号。在任何时候，我们都会看到一个可能包含5个或更多ruby的列表，我们可以轻松地键入一个数字而不是X.X.X。这也有助于rvmgemset。 最佳答案 这在RVM2.0中是可能的=>https://docs.google.com/document/d/1xW9GeEpLOWPcddDg_hOPvK4oeLxJmU3Q5FiCNT7nTAc/edit?usp=sharing-知道链接的任何人都可以发表评论

  5. ruby - rspec 需要 .rspec 文件中的 spec_helper - 2

    我注意到像bundler这样的项目在每个specfile中执行requirespec_helper我还注意到rspec使用选项--require，它允许您在引导rspec时要求一个文件。您还可以将其添加到.rspec文件中，因此只要您运行不带参数的rspec就会添加它。使用上述方法有什么缺点可以解释为什么像bundler这样的项目选择在每个规范文件中都需要spec_helper吗？ 最佳答案 我不在Bundler上工作，所以我不能直接谈论他们的做法。并非所有项目都checkin.rspec文件。原因是这个文件，通常按照当前的惯例，只

  6. ruby - 如何在 Lion 上安装 Xcode 4.6，需要用 RVM 升级 ruby - 2

    我实际上是在尝试使用RVM在我的OSX10.7.5上更新ruby，并在输入以下命令后:rvminstallruby我得到了以下回复:Searchingforbinaryrubies,thismighttakesometime.Checkingrequirementsforosx.Installingrequirementsforosx.Updatingsystem.......Errorrunning'requirements_osx_brew_update_systemruby-2.0.0-p247',pleaseread/Users/username/.rvm/log/138121

  7. ruby - 无法在 60 秒内获得稳定的 Firefox 连接 (127.0.0.1 :7055) - 2

    我使用的是Firefox版本36.0.1和Selenium-Webdrivergem版本2.45.0。我能够创建Firefox实例，但无法使用脚本继续进行进一步的操作无法在60秒内获得稳定的Firefox连接(127.0.0.1:7055)错误。有人能帮帮我吗？ 最佳答案 我遇到了同样的问题。降级到firefoxv33后一切正常。您可以找到旧版本here 关于ruby-无法在60秒内获得稳定的Firefox连接(127.0.0.1:7055)，我们在StackOverflow上找到一个类

  8. java - 我的模型类或其他类中应该有逻辑吗 - 2

    我只想对我一直在思考的这个问题有其他意见，例如我有classuser_controller和classuserclassUserattr_accessor:name,:usernameendclassUserController//dosomethingaboutanythingaboutusersend问题是我的User类中是否应该有逻辑user=User.newuser.do_something(user1)oritshouldbeuser_controller=UserController.newuser_controller.do_something(user1,user2)我

  9. ruby - 为什么在 ruby​​ 中创建 Rational 不需要新方法 - 2

    这个问题在这里已经有了答案:关闭10年前。PossibleDuplicate:Rubysyntaxquestion:Rational(a,b)andRational.new!(a,b)我正在阅读ruby镐书，我对创建有理数的语法感到困惑。Rational(3,4)*Rational(1,2)产生=>3/8为什么Rational不需要new方法(我还注意到例如我可以在没有new方法的情况下创建字符串)？

  10. 区块链之加解密算法&数字证书 - 2

    目录一.加解密算法数字签名对称加密DES(DataEncryptionStandard)3DES(TripleDES)AES(AdvancedEncryptionStandard)RSA加密法DSA(DigitalSignatureAlgorithm)ECC(EllipticCurvesCryptography)非对称加密签名与加密过程非对称加密的应用对称加密与非对称加密的结合二.数字证书图解一.加解密算法加密简单而言就是通过一种算法将明文信息转换成密文信息，信息的的接收方能够通过密钥对密文信息进行解密获得明文信息的过程。根据加解密的密钥是否相同，算法可以分为对称加密、非对称加密、对称加密和非

随机推荐