算法:从n个数组(队列)中找出k个数的最小和

假设有n个正数队列.我需要从这些队列中选择最少的k个数字.请注意,这些是队列,因此排序很重要,一次只能从任何队列中选择第一个数字.一旦选择了该号码并从队列中删除,我们就可以继续进入该队列中的下一个号码.因此不允许排序(顺序很重要).

例如:

找到两个数字的最小总和

2 12 3 4 
8 2 2
10 10

在上面的例子中,我可以从第一个队列中选择2,从第二个队列中选择8个,从第二个队列中选择8和2.这两个选择都给出10.

例2:

找到两个数字的最小总和

4 15 2
8 2 2
10 10

在上面的例子中,必须从第二个列表中选择8和2.

我首先考虑合并K排序列表的行,但它不起作用.我只能想到一种有效的方法.它是尝试所有队列中的所有组合.有人可以建议更好的方式或指导我吗？

我们F(qs, k)是从队列中选择k个最小总和qs.然后:

F([], k) = 0 if k == 0, otherwise +infinity.
F([q] + qs, k) = min_i(q[0] + q[1] + ... + q[i-1] + F(qs, k-i) for i in 0...k)

也就是说,如果您没有剩余队列,则最小总和为0,否则,您可以i从第一个队列和k-i其他队列中获取数字.

这可以通过构建(n,k)表来有效地使用动态编程来解决,其中n是队列的数量.在Python 2中:

def F(qs, n, k, cache):
    if k == 0:
        return 0
    if n == 0:
        return 1e12
    if (n, k) not in cache:
        best = 1e12
        s = 0
        for i in xrange(k+1):
            if i > len(qs[len(qs)-n]):
                break
            if i > 0:
                s += qs[len(qs)-n][i-1]
            best = min(best, s + F(qs, n-1, k-i, cache))
        cache[n, k] = best
    return cache[n, k]

egs = [
    (2, [[2, 2, 3, 4], [8, 2, 2], [10, 10]]),
    (2, [[4, 15, 2], [8, 2, 2], [10, 10]]),
    (3, [[100, 100, 100], [101, 101, 2]])
]

for k, qs in egs:
    print k, qs
    print F(qs, len(qs), k, dict())
    print

打印

2 [[2, 2, 3, 4], [8, 2, 2], [10, 10]]
4

2 [[4, 15, 2], [8, 2, 2], [10, 10]]
10

3 [[100, 100, 100], [101, 101, 2]]
204