草庐IT

c++ - 获得最佳组合的算法

coder 2024-07-06 原文

我有 ID 为 1、3、4、5、6、7 的项目。现在我有如下数据。 每行都有一个 offerId。 Array of Ids 由数组中的 ID 组合组成。 Discount 是该 offerId

的值 
offerId : Array of Ids     : Discount
o1      : [1]              : 45
o2      : [1 3 4]          : 100
o3      : [3 5]            : 55
o4      : [5]              : 40
o5      : [6]              : 30
o6      : [6 7]            : 20

现在我必须选择所有提供最佳 ID 组合的 offerId，即最大总折扣。

例如在上面的例子中:可能的结果可能是:

[o2, o4, o5] 最大折扣为 170(100 + 40 + 30)。

注意。结果 offerId 应该是这样的 ID 不重复。 o2,o4,o6 的示例 id 为 [1,3,4]、[5]、[6] 都是不同的。

其他组合可以是: o1, o3, 06 其中 ids 是 [1], [3,5], [6,7] 但是总数是 120(45+55+20) 小于 170 和前面的例子一样。

我需要一个算法/代码来帮助我识别 combination of offerIds 这将提供 maximum discount ，考虑到每个报价都应该包含不同的 Ids.

注意 我正在用 go 语言编写代码。但是任何语言的解决方案/逻辑都会有所帮助。

注意:我希望我能够正确解释我的要求。如果需要任何额外信息，请发表评论。谢谢。

最佳答案

这是一个动态规划解决方案，它针对每个可能的 ID 子集，找到折扣最大的报价组合。 这将是伪代码。

让我们的优惠成为包含字段offerNumber、setOfItems 和discount 的结构。 为了实现的目的，我们首先用从零到不同可能项目的数量(比如 k)减一的整数重新枚举可能的项目。 之后，我们可以用长度为k的二进制数来表示setOfItems。 例如，如果 k = 6 和 setOfItems = 1011102，则此集合包括项目 5、3、2 和 1，不包括项目 4 和0，因为第 5、3、2 和 1 位是 1，而第 4 和 0 位是零。

现在让 f[s] 成为我们可以使用恰好集合 s 的项目获得的最佳折扣。 这里，s 可以是 0 到 2k - 1 之间的任何整数，代表 2k 可能的子集之一。 此外，让 p[s] 成为优惠列表，它们一起允许我们为项目集 s 获得折扣 f[s] . 算法如下。

initialize f[0] to zero, p[0] to empty list
initialize f[>0] to minus infinity
initialize bestF to 0, bestP to empty list
for each s from 0 to 2^k - 1:
    for each o in offers:
        if s & o.setOfItems == o.setOfItems:  // o.setOfItems is a subset of s
            if f[s] < f[s - o.setOfItems] + o.discount:  // minus is set subtraction
                f[s] = f[s - o.setOfItems] + o.discount
                p[s] = p[s - o.setOfItems] append o.offerNumber
                if bestF < f[s]:
                    bestF = f[s]
                    bestP = p[s]

之后，bestF 是可能的最佳折扣，而 bestP 是获得该折扣的报价列表。

复杂度为 O (|offers| * 2k)，其中 k 是项目总数。

这是另一个渐近相同的实现，但在大多数子集无法访问的情况下在实践中可能会更快。 是“前向”而不是“后向”的动态规划。

initialize f[0] to zero, p[0] to empty list
initialize f[>0] to -1
initialize bestF to 0, bestP to empty list
for each s from 0 to 2^k - 1:
    if f[s] >= 0:  // only for reachable s
        if bestF < f[s]:
            bestF = f[s]
            bestP = p[s]
        for each o in offers:
            if s & o.setOfItems == 0:  // s and o.setOfItems don't intersect
                if f[s + o.setOfItems] < f[s] + o.discount:  // plus is set addition
                    f[s + o.setOfItems] = f[s] + o.discount
                    p[s + o.setOfItems] = p[s] append o.offerNumber

关于c++ - 获得最佳组合的算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/39791544/

amp43codesetOfItemssectionc++calgorithmgo

有关c++ - 获得最佳组合的算法的更多相关文章

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

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

  2. 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

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

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

  4. 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上找到一个类

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

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

  6. ruby - 使用 `+=` 和 `send` 方法 - 2

    如何将send与+=一起使用？a=20;a.send"+=",10undefinedmethod`+='for20:Fixnuma=20;a+=10=>30 最佳答案 恐怕你不能。+=不是方法，而是语法糖。参见http://www.ruby-doc.org/docs/ProgrammingRuby/html/tut_expressions.html它说Incommonwithmanyotherlanguages,Rubyhasasyntacticshortcut:a=a+2maybewrittenasa+=2.你能做的最好的事情是:

  7. ruby - 如何计算 Liquid 中的变量 +1 - 2

    我对如何计算通过{%assignvar=0%}赋值的变量加一完全感到困惑。这应该是最简单的任务。到目前为止，这是我尝试过的:{%assignamount=0%}{%forvariantinproduct.variants%}{%assignamount=amount+1%}{%endfor%}Amount:{{amount}}结果总是0。也许我忽略了一些明显的东西。也许有更好的方法。我想要存档的只是获取运行的迭代次数。 最佳答案 因为{{incrementamount}}将输出您的变量值并且不会影响{%assign%}定义的变量，我

  8. ruby-on-rails - Rails 中同一个类的多个关联的最佳实践？ - 2

    我认为我的问题最好用一个例子来描述。假设我有一个名为“Thing”的简单模型，它有一些简单数据类型的属性。像...Thing-foo:string-goo:string-bar:int这并不难。数据库表将包含具有这三个属性的三列，我可以使用@thing.foo或@thing.bar之类的东西访问它们。但我要解决的问题是当“foo”或“goo”不再包含在简单数据类型中时会发生什么？假设foo和goo代表相同类型的对象。也就是说，它们都是“Whazit”的实例，只是数据不同。所以现在事情可能看起来像这样......Thing-bar:int但是现在有一个新的模型叫做“Whazit”，看起来

  9. ruby-on-rails - 向 Rails 3 添加 Ruby 扩展方法的最佳实践？ - 2

    我有一个要在我的Rails3项目中使用的数组扩展方法。它应该住在哪里？我有一个应用程序/类，我最初把它放在(array_extensions.rb)中，在我的config/application.rb中我加载路径:config.autoload_paths+=%W(#{Rails.root}/应用程序/类)。但是，当我转到railsconsole时，未加载扩展。是否有一个预定义的位置可以放置我的Rails3扩展方法？或者，一种预先定义的方式来添加它们？我知道Rails有自己的数组扩展方法。我应该将我的添加到active_support/core_ext/array/conversion

  10. ruby - 最佳原则中的原则 - 2

    我似乎经常遇到一些设计问题，但我不知道是什么是真的很合适。一方面我经常听到我应该限制耦合和坚持单一职责，但当我这样做时，我常常发现它很困难到在需要时将信息获取到程序的一部分。为了例如，classSingerdefinitialize(name)@name=nameendattr:nameend那么Song应该是:classSongdefnew(singer)@singer=singerendend或classSongdefnew(singer_name)@singer_name=singer_nameendend后者耦合性小，按道理应该用。但如果我以后发现宋有什么需要了解更多歌手，我的

随机推荐