算法得到最佳组合 [英] Algorithm to get best combination

问题描述

我有ID 1,3,4,5,6,7 的商品。现在我有如下的数据。
每行有一个offerId。 Ids数组由数组中的 ID 组合而成。 折扣是指 offerId $ b $

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


现在我必须选择所有offerIds，这些offerIds可以给我最佳的Ids组合，即最大总折扣。

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

[o2，o4，o5]最大折扣是 170（100 + 40 + 30）。

注意。 offerId的结果应该是这样，Ids不会重复。示例 o2，o4，o6 ids是[1,3,4]，[5]，[6]都是不同的。

其他组合可以是：
o1，o3，06 ，其id是[1]，[3,5]，[6， 7]然而，总数是120（45 + 55 + 20），小于以前的情况< 170 。

我需要一个算法/代码，它可以帮助我识别 offerIds 的组合，它将给出最大折扣，考虑到每个要约应包含不同的 Ids 。

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

注：我希望我能够正确解释我的要求。请评论是否需要任何额外的信息。感谢。

解决方案

以下是一个动态编程解决方案，针对每个可能的ID子集，折扣是最大可能的。
这将是伪代码。

让我们的报价为结构字段 offerNumber ， setOfItems 和折扣。
为了实现的目的，我们首先将可能的项目从零到不同可能项目的数量（比如 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之间的任何整数，代表2 中的一个可能的子集。
此外，让 p [s] 成为允许我们获得折扣的报价列表 f [s] 为项目集合 s 。
算法如下。

 将f [0]初始化为零，p [0]为空列表
将f [> 0]初始化为负无穷
初始化bestF为0，bestP为空列表
对于每个s从0到2 ^ k  -  1：
对于每个o提供：
如果s& o.setOfItems == o.setOfItems：// o.setOfItems是s 
的一个子集，如果f [s]< f [s  -  o.setOfItems] + o.discount：//减去设置减法
f [s] = f [s  -  o.setOfItems] + o.discount 
p [s] = p [s -  o.setOfItems]追加o.offerNumber 
 if bestF< f [s]：
 bestF = f [s] 
 bestP = p [s] 
  

之后， bestF 是最好的折扣， bestP 是让我们即$折扣。

复杂度为O（| offers | * 2 ^k ）其中 k 是项目总数。

以下是另一个实现渐近相同的实现，但在大多数子集无法访问的情况下实践中可能会更快。
它是前进而不是后退动态编程。

 将f [0]初始化为零，p [0]为空列表
初始化f [> 0]为-1 
初始化bestF为0，bestP为空列表
对于每个s从0到2 ^ k  -  1：
如果f [s]> = 0：//仅适用于可达s 
 if bestF < f [s]：
 bestF = f [s] 
 bestP = p [s] 
 for offer中的每个o：
如果s& o.setOfItems == 0：// s和o.setOfItems不相交
如果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 
  

I have items with ID 1, 3, 4, 5, 6, 7. Now I have data like following. There is an offerId for each row. Array of Ids consist of combination of the ID in an array. Discount is the value for that 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

Now I have to select all the offerIds which give me best combination of Ids i.e. maximum total discount.

For example in above case : possible results can be:

[o2, o4, o5] maximum discount is 170(100 + 40 + 30).

Note. the result offerId should be such that Ids don't repeat. Example for o2,o4,o6 ids are [1,3,4], [5], [6] all are distinct.

Other combination can be : o1, o3, 06 for which ids are [1], [3,5], [6,7] However the total is 120(45+55+20) which is less then 170 as in previous case.

I need an algorithm/code which will help me to identify combination of offerIds which will give maximum discount , considering that each offer should contain distinct Ids.

NOTE I am writing my code in go language. But solutions/Logic in any language will be helpful.

NOTE : I hope I am able to explain my requirement properly. please comment if any extra information is required. Thanks.

解决方案

Here is a dynamic programming solution which, for every possible subset of IDs, finds the combination of offers for which the discount is maximum possible. This will be pseudocode.

Let our offers be structures with fields offerNumber, setOfItems and discount. For the purposes of implementation, we first renumerate the possible items by integers from zero to number of different possible items (say k) minus one. After that, we can represent setOfItems by a binary number of length k. For example, if k = 6 and setOfItems = 101110₂, this set includes items 5, 3, 2 and 1 and excludes items 4 and 0, since bits 5, 3, 2 and 1 are ones and bits 4 and 0 are zeroes.

Now let f[s] be the best discount we can get using exactly set s of items. Here, s can be any integer between 0 and 2^k - 1, representing one of the 2^k possible subsets. Furthermore, let p[s] be the list of offers which together allow us to get discount f[s] for the set of items s. The algorithm goes as follows.

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]

After that, bestF is the best possible discount, and bestP is the list of offers which get us that discount.

The complexity is O (|offers| * 2^k) where k is the total number of items.

Here is another implementation which is asymptotically the same, but might be faster in practice when most subsets are unreachable. It is "forward" instead of "backward" dynamic programming.

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

这篇关于算法得到最佳组合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！