algorithm - 从多个列表的元素中找出 (100) 个最高总和

Question

我有以下问题(在我的版本中有一些约束可能使问题更容易解决，但一般的解决方案也很好):

我有 4 个列表，其中包含 10 个条目。第一个列表包含 0 到 6 之间的整数条目，其他三个列表包含 0 到 3 之间的条目。我现在必须找到这四个列表元素的 100 个最佳组合。一个组合由 4 个值的总和组成，每个列表一个。请注意，我不仅需要知道结果元素的值，还需要知道它们的组成方式，因为与这些值相关的信息更多。

示例 1:

list A: 6, 3, 2, 2, 1, 0, 0, 0, 0
list B: 3, 2, 0, 0, 0, 0, 0, 0, 0
list C: 2, 2, 0, 0, 0, 0, 0, 0, 0
list D: 3, 1, 1, 1, 1, 1, 0, 0, 0

在这种情况下，五个最佳组合是:

• 14 (A[0] + B[0] + C[0] + D[0])
• 14 (A[0] + B[0] + C[1] + D[0])
• 13 (A[0] + B[1] + C[0] + D[0])
• 13 (A[0] + B[1] + C[1] + D[0])
• 12 (A[0] + B[0] + C[0] + D[1])

请注意，我已经对列表的条目进行了排序，因为这可能是解决此问题的大多数算法的第一步。

简单的解决方案

最简单的解决方案是形成所有 10,000 种可能的组合，然后从中选出一百个最佳组合。甚至不必对 10.000 种可能的组合进行排序。可以先扫描数组并分析哪个值出现的频率。然后可以在下一次扫描值时选择一百个最佳值(及其进一步的属性)。

一个不起作用的解决方案

我想到的另一个想法如下:第一个必须对列表进行排序。在每个列表中，我想找到一个索引，它将那些可以为解决方案做出贡献的条目与不能为解决方案做出贡献的条目分开。当必须在示例 1 中找到四个最佳组合时，例如可以选择列表 B 和 C 的前两个元素，以及列表 的第一个>A 和 D这将产生:

A: 6
B: 3, 2
C: 3, 2
D: 3

这些子列表的所有组合都会产生最优解。然而，这并不总是可能的，如以下示例所示:

示例 2:

(这次只有两个列表)

list A: 6, 5, 5, 0, 0, ...
list B: 3, 1, 1, 0, 0, ...

在这里，最好的四种解决方案是

• 6 + 3
• 5 + 3
• 5 + 3
• 6 + 1

然而，这个解决方案无法通过索引找到，它将四个组合与所有其他组合分开。

Answer 1

让我尝试以更简洁的方式重新表述现有答案(Evgeny Kluev，solendil)。

解决方案是 Best-first search从配置 (0,0,0,0) 开始。搜索树的分支因子为 4(列表数)。

在 (0,0,0,0) 处，您知道下一个最佳配置是 (1,0,0,0)、(0,1,0,0)、(0,0,1 ,0) 或 (0,0,0,1)。因此，您将搜索树的这些“叶子”放入一个优先级队列中，该队列按每个配置的好坏排序。叶子队列是下一个最佳配置候选队列。

然后你从队列中取出最好的配置添加到答案列表中并更新队列。例如，如果 (0,0,1,0) 是下一个最好的，则将其从队列中取出然后将它的 child - (1,0,1,0), (0,1,1,0), (0,0,2,0), (0,0,1,1) - 添加到队列中。