挑战：如何存储大量集合来快速计算每个集合中元素所取值的总和？

Question

我想征求一下您的意见。我应该使用哪种数据结构和算法来有效地解决以下问题？

\n

问题：

\n

\n

给定 M (10\xe2\x89\xa4 M \xe2\x89\xa41000) 个元素和由这些元素构建的N个集合。每个集合中没有重复的元素。集合的数量可能会超过几万，这与元素的数量有一定的关系。

\n

输入M个元素的值X（double类型，0\xe2\x89\xa4 X \xe2\x89\xa41）

\n

找出N个集合中元素值之和最大的集合。

\n

\n

例如：

\n

\n

前提条件：给定 5 个元素和 5 个集合

\n

X = (A,B,C,D,E), S = [(A,B),(C,D),(B,C,E),(B,D,E),(A,C,D,E)]\n

\n

\n

\n

输入：X的值为

\n

X = (0.2, 0.8, 0.6, 0.3, 0.5)\n

\n

\n

\n

结果：元素值之和最大的集合是

\n

sum(B,C,E) = 0.8 + 0.6 + 0.5 = 1.9 \n

\n

\n

在某些集合中，存在公共子序列，可以将它们组合并存储，以降低求和算法的空间复杂度和时间复杂度。您建议使用什么数据结构来存储这些集合？求和算法的时间复杂度是多少？

\n

Answer 1

我认为一个好的开始是建立一个所有输入集的树：

“空”根，然后每个集合中的每个第一个元素有 1 个子元素，然后根据输入集合，如示例：子 A 将有子 B 和 C，子 B 将有 C 和 D 等等...

要找到最佳总和，请在树上运行 DFS，同时用 X 中的值替换每个元素，并记住具有最高总和的叶子的路线。

使用树作为数据结构，可以为您提供“假记忆”，因为您可以计算并保留每个节点的总和，而不需要重新计算它。