我有以下问题（在我的版本中，有一些限制可能使问题更容易解决，但一般的解决方案也很好）：
我有 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
但是，无法使用索引找到此解决方案，索引将四种组合与所有其他组合分开。