从多个列表中查找元素中的(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

该解决方案使用两种数据结构：

1. 优先级队列，其中列表元素的总和是键，列表索引的元组是值。
2. 包含列表索引元组的哈希集。

算法：

1. 对每个列表进行排序。
2. 将包含每个列表的第一个元素的元组放入队列中。
3. 当哈希集包含的元组少于 100 个时，执行步骤 4 和 5。
4. 从队列中弹出最大的项，检查哈希集是否包含相应的索引元组（T）。如果找到这样的元组，则重复步骤4，否则继续步骤5。
5. 将元组 T 插入哈希集中。创建 N 个元组（其中 N 是列表的数量），每个元组的 N-1 个索引等于 T 中的对应索引，并且其中一个索引大于 1，并将这些元组插入队列中。

实现优先级队列（对于此问题）的最佳方法可能是使用有序容器（二叉搜索树或跳跃列表），首先按列表元素的总和排序，然后按列表索引排序。这使得不需要单独的哈希集，因为该容器可以在将重复项添加到队列之前检测到重复项。