使用每组中的一个数字，查找多组数字的总和

Question

使用每组中的一个数字，查找多组数字的总和

listalgorithmmathiteratorlazy-evaluation

5

背景

嗨，我正在尝试解决一个编程问题，以下是我卡在的问题：

假设您有多个数字列表。所有列表都按递减顺序排序。现在，您必须从每个列表中取一个数字，以使总和最大。

到此为止还很简单，要解决这个问题，您只需要从每个列表中取出第一个数字即可。

但是，现在我需要第二大的总和，仍然只能从每个列表中选取一个数字。为了实现这一点，我将从每个列表中选择第一个元素，但对于差异最小的第一个和第二个数字之间的列表，将使用第二个数字。

这仍然相当容易。

问题

但我需要一个迭代器，可以对每个可能的总和进行迭代，每个列表只用选择一个数字并按递减顺序排序。
出于性能原因，不可能计算每个总和然后对其进行排序。算法必须已经按递减顺序提供总和。如果有多个组合可以得到该总和，则必须多次返回该总和。

附加要求

迭代器应该是惰性的（仅在需要时才计算下一个总和）。
列表已经是惰性的，这意味着您应该尽量少地要求计算适合的和。

示例

对于以下列表：

List 1: [5, 2, 1]
List 2: [10, 2]
List 3: [6, 1]

迭代器应该返回：

[5, 10, 6] = 21
[2, 10, 6] = 18
[1, 10, 6] = 17
[5, 10, 1] = 16
[5,  2, 6] = 13
[2, 10, 1] = 13
[1, 10, 1] = 12
[2,  2, 6] = 10
[1,  2, 6] = 9
[5,  2, 1] = 8
[2,  2, 1] = 5
[1,  2, 1] = 4

你对于寻找第二大的和的想法似乎是正确的。为了得出一个解决方案，你应该思考一下如何从中找到第三大的和，然后将其推广。当你找到一个模式后，你可以更加专注于优化。作为提示，你可以考虑选择下一个值并生成下一个可能的选择的轮廓，就像 bfs 一样。 - wLui155

我尝试的方法是只取比之前更好的元素。这导致跳过了许多总和。下一个想法是选择最少减少的那个，将其固定，然后按递减顺序使用其他元素。这导致了错误的顺序。我目前的尝试是每次在其中一个列表中生成新项目时，我会强制执行其他列表中已使用的所有项目。这不完全是懒惰的，但足够懒惰。我现在想知道是否有真正的懒惰方法。 - Pilikio

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Pilikio · Accepted Answer

首先，感谢wlui155的帮助。

对于任何有兴趣的人，我编写了一个BFS算法，其操作如下：

定义：
Entry：包含已使用数字和总和索引的结构体
BSet：有序集合，只能包含唯一的条目

算法：

从BSet中弹出总和最大的Entry
为每个列表创建一个克隆
在每个克隆中不同的索引向前移动一个
将新条目放入BSet中
打印当前Entry
转到1。

现在，您只需要确保在弹出条目后不再出现该条目。这可以通过包含当前总和的所有组合的单独集合来实现。一旦当前总和变小，就可以清除此集合。

如果您有改进这个算法的想法，欢迎告诉我。

使用每组中的一个数字，查找多组数字的总和

背景

问题

附加要求

示例

评论