获得最佳组合的算法

Question

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.

Answer 1

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