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

Question

我有 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 语言编写代码。但是任何语言的解决方案/逻辑都会有所帮助。

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

Answer 1

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

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

现在让 f[s] 成为我们可以使用恰好集合 s 的项目获得的最佳折扣。这里，s 可以是 0 到 2^k - 1 之间的任何整数，代表 2^k 可能的子集之一。此外，让 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| * 2^k)，其中 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