获得最佳组合的算法

一尘不染

获得最佳组合的算法

我有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,o6id的示例为[1,3,4]，[5]，[6]都是不同的。

其他组合可以是： o1, o3, 06其id为[1]，[3,5]，[6,7]，但是总数为120（45 + 55 + 20），170比以前的情况要少。

考虑到每个报价都应包含不同的信息，我需要一个算法/代码来帮助我确定combination of offerIds要给出的maximum discount报价Ids。

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

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

阅读 692

2020-07-02

共1个答案

一尘不染

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

让我们的报价成为具有字段的结构offerNumber，setOfItems并且discount。为了实现目的，我们首先通过从零到不同的可能项目数（例如k）减去1
的整数重新枚举可能的项目。之后，我们可以setOfItems用length的二进制数表示k。例如，如果k= 6和setOfItems=
101110 2，则此集合包括项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]我们提供要约清单，这些清单可以使我们共同获得f[s]一组商品的折扣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

2020-07-02