小编ten*_*ity的帖子

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

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

\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
Run Code Online (Sandbox Code Playgroud)\n
\n
\n

输入:X的值为

\n
X = (0.2, 0.8, 0.6, 0.3, 0.5)\n
Run Code Online (Sandbox Code Playgroud)\n
\n
\n

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

\n
sum(B,C,E) = 0.8 + 0.6 + 0.5 = 1.9 \n
Run Code Online (Sandbox Code Playgroud)\n
\n

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

\n

algorithm graph-theory graph dynamic-programming data-structures

5
推荐指数
1
解决办法
107
查看次数