K-最大双重选择最大
想象一下，你有两个袋（ A 和 B ）使用 N 和 M 球，分别在里面。每个球具有已知数值（利润）。你被要求提取（带替换）这对球的最大总利润（由所选球的乘法给出）。
最好的提取是显而易见的：从 A ，以及从 B
的问题是当你被要求提供第2或第k个最好的选择。继previous方法，你应该选择 A 的最大价值球和 B 不重复的选择。
这可能是笨拙地解决了计算每一个可能的选项的值，订货和订货它（例如在python）：
高清解决方案（A，B，K）：
如果K＆LT; 1：
返回0
池= []
对于在答：
对B在B：
pool.append（A * B）
pool.sort（反向=真）
如果K＆GT; LEN（池）：
返回0
回报池[K-1]
这工作，但它的最坏时间复杂度为 O（N * M *日志（M×M））和我打赌有更好的解决方案。
我伸手基于表的解决方案，其中 A 和 B 元素被产生更高的价值排序，以降低和每个值已关联的索引重新presenting下一个值从其他列进行测试。最初，这个表看起来像：
从 A 的第一个元素是 25 和它进行测试（指数2，从B = 0 ）对 20 选择让 25 * 20 = 500 是第一个最大的选择和，后增加了索引来检查，该表变为：
使用这些指标，我们有一个快捷的方式，以获得最佳的候选者：
25 * 20 = 500 #first从A和第二选自B
20 * 20 = 400 #second从A和首先会从B
我试图code此解决方案：
高清解决方案（A，B，K）：
如果K＆LT; 1：
返回0
SA =排序（A，反向=真）
SB =排序（B，反向=真）
对于k中的xrange（K）：
I = xfrom
J = yfrom
如果我＆GT; = N和J＆GT; = N：
RET = 0
打破
最好=无
而I＆LT; N和J＆LT; N：
选中=假
#From离开
nexti = I
nextj = SA [I] [1]
一个= SA [nexti] [0]
B =某人[nextj] [0]
如果最好的是无或最佳[2]其中，A * B：
选定= TRUE
最好= [nexti，nextj，A * B，'升']
#From权
nexti =某人[J]。[1]
nextj = j的
一个= SA [nexti] [0]
B =某人[nextj] [0]
如果最好的是无或最佳[2]其中，A * B：
选定= TRUE
最好= [nexti，nextj，A * B，为'r']
＃继续寻找？
如果没有选择或者ABS（最好[0] - 最佳[1]）2：
打破
I =分钟（最好[：2]）+ 1
J =
打印（继续，最好的，选择，I，J）
＃冲啊
打印（最好）
如果最好的[3] ==L：
DX〔最好[0] [1] =最好[1] 1
镝[最好[1] [1] + = 1
其他：
DX〔最好[0] [1] + = 1
镝[最好[1] [1] =最好[0] 1
如果DX〔最好[0] [1]≥=正：
xfrom =最好的[0] +1
如果镝[最好[1] [1]≥=正：
yfrom =最好的[1] +1
RET =最好[2]
返回RET
但它并没有为上线Codility法官的工作（我有没有提到这是解决一个的部分，已经过期，Codility挑战？Sillicium 2014年）
我的问题是：
是第二种方法一个未完成的很好的解决方案？如果是这样的情况下，我可能会错过任何线索？ 请您知道该问题的任何更好的办法？ 解决方案您需要保持优先级队列。
您开始使用（SA [0]，某人[0]），然后移动到（SA [0]，某人[1] ）和（SA [1]，某人[0]）。如果（SA [0] *某人[1]）＆GT; （SA [1] *某人[0]），我们可以说一下（SA [0]，某人[2]）和（SA [1]，某人[0]）？
答案是否定的。因此，我们必须保持优先级队列，并删除每个之后（SA [我]，某人[J]。）（这样 SA [我] *某人[J] 是最大的队列中），我们必须添加到优先级队列（SA [我 - 1]，某人[J]。）和（SA [I]，SB [J - 1]），然后重复此 K 次
顺便说一句，我给了这个算法为answer以一个不同的问题。该算法可能看起来是在第一不同，但本质上它解决了同样的问题。
Imagine you have two sacks (A and B) with N and M balls respectively in it. Each ball with a known numeric value (profit). You are asked to extract (with replacement) the pair of balls with the maximum total profit (given by the multiplication of the selected balls).
The best extraction is obvious: Select the greatest valued ball from A as well as from B.
The problem comes when you are asked to give the 2nd or kth best selection. Following the previous approach you should select the greatest valued balls from A and B without repeating selections.
This can be clumsily solved calculating the value of every possible selection, ordering and ordering it (example in 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]
This works but its worst time complexity is O(N*M*Log(M*M)) and I bet there are better solutions.
I reached a solution based on a table where A and B elements are sorted from higher value to lower and each of these values has associated an index representing the next value to test from the other column. Initially this table would look like:
The first element from A is 25 and it has to be tested (index 2 select from b = 0) against 20 so 25*20=500 is the first greatest selection and, after increasing the indexes to check, the table changes to:
Using these indexes we have a swift way to get the best selection candidates:
25 * 20 = 500 #first from A and second from B
20 * 20 = 400 #second from A and first from B
I tried to code this solution:
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
But it did not work for the on-line Codility judge (Did I mention this is part of the solution to an, already expired, Codility challenge? Sillicium 2014)
My questions are:
Is the second approach an unfinished good solution? If that is the case, any clue on what I may be missing? Do you know any better approach for the problem? 解决方案You need to maintain a priority queue.
You start with (sa[0], sb[0]), then move onto (sa[0], sb[1]) and (sa[1], sb[0]). If (sa[0] * sb[1]) > (sa[1] * sb[0]), can we say anything about the comparative sizes of (sa[0], sb[2]) and (sa[1], sb[0])?
The answer is no. Thus we must maintain a priority queue, and after removing each (sa[i], sb[j]) (such that sa[i] * sb[j] is the biggest in the queue), we must add to the priority queue (sa[i - 1], sb[j]) and (sa[i], sb[j - 1]), and repeat this k times.
Incidentally, I gave this algorithm as an answer to a different question. The algorithm may seem to be different at first, but essentially it's solving the same problem.
