k-最大双重选择

Question

想象一下，你有两个袋子（A 和 B），里面分别有 N 和 M 个球。每个球都有一个已知的数字值（利润）。你的任务是从中提取出一对球，使得它们的总利润最大（这个总利润是通过选择的两个球的值相乘得到的）。

最简单的选择显而易见：从 A 和 B 中各选出一个值最大的球。

问题在于，当你需要给出第二个或第 k 个最佳选择时，就不那么简单了。按照之前的方法，你应该从 A 和 B 中选择最大的球，但不能重复选择。

这个问题可以通过计算每一种可能的选择，进行排序来解决（以下是一个 Python 示例）：

def solution(A,B,K):
    if K < 1:
        return 0
    pool = []
    for a in A:
        for b in B:
            pool.append(a*b)
    pool.sort(reverse=True)
    if K>len(pool):
        return 0
    return pool[K-1]

这种方法有效，但它的最坏时间复杂度是 O(N*M*Log(M*M))，我敢打赌还有更好的解决方案。

我找到了一种基于表格的解决方案，其中 A 和 B 的元素按从高到低排序，每个值都有一个索引，表示下一个要从另一列测试的值。最开始这个表格看起来是这样的：

enter image description here

A 中的第一个元素是 25，它需要与 20（index 2 select from b = 0）进行比较，所以 25*20=500 是第一个最大的选择。然后，增加索引进行检查，表格变成：

enter image description here

利用这些索引，我们可以快速找到最佳选择的候选者：

25 * 20 = 500 #first from A and second from B
20 * 20 = 400 #second from A and first from B

我尝试编写这个解决方案的代码：

def solution(A,B,K):
    if K < 1:
        return 0
    sa = sorted(A,reverse=true)
    sb = sorted(B,reverse=true)

    for k in xrange(K):
        i = xfrom
        j = yfrom
        if i >= n and j >= n:
                ret = 0
                break
        best = None
        while i < n and j < n:
                selected = False
                #From left
                nexti = i
                nextj = sa[i][1]
                a = sa[nexti][0]
                b = sb[nextj][0]
                if best is None or best[2]<a*b:
                        selected = True
                        best = [nexti,nextj,a*b,'l']
                #From right
                nexti = sb[j][1]
                nextj = j
                a = sa[nexti][0]
                b = sb[nextj][0]
                if best is None or best[2]<a*b:
                        selected = True
                        best = [nexti,nextj,a*b,'r']
                #Keep looking?
                if not selected or abs(best[0]-best[1])<2:
                        break
                i = min(best[:2])+1
                j = i
                print("Continue with: ", best, selected,i,j)
        #go,go,go
        print(best)
        if best[3] == 'l':
            dx[best[0]][1] = best[1]+1
            dy[best[1]][1] += 1
        else:
            dx[best[0]][1] += 1
            dy[best[1]][1] = best[0]+1
        if dx[best[0]][1]>= n:
            xfrom = best[0]+1
        if dy[best[1]][1]>= n:
            yfrom = best[1]+1
        ret = best[2]

    return ret

但它在在线的 Codility 评测中没有通过（我提到过这是一个已经过期的 Codility 挑战的部分解决方案吗？Sillicium 2014）。

我的问题是：

第二种方法是一个未完成的好方案吗？如果是这样，你能给我一些提示，告诉我可能缺少什么吗？
你知道有什么更好的方法来解决这个问题吗？

时间复杂度排序算法编程挑战组合优化 k-最大双重选择最大利润值索引选择问题

k-最大双重选择

2 个回答

撰写回答