gpt4 book ai didi

algorithm - 子集上定义的函数总和

转载 作者:塔克拉玛干 更新时间:2023-11-03 03:54:23 26 4
gpt4 key购买 nike

我想知道他们是否有解决以下问题的快速方法。我有一个数以千计的代码列表 (A0, A1, A2, ...)。大约一百万个不同的组合 (A0-A1, A2-A10, A1-A2-A10, ...) 具有正值。让值表示为 f(A0-A1)。请注意,并非所有组合都具有附加值。

对于每个列出的组合,我想计算附加到包含给定组合的每个集合的值的总和。例如,对于 A2-A10,计算

g(A2-A10) = f(A2-A10) + f(A1-A2-A10) + ...

我想以最小的时间复杂度来完成这项工作。一个更简单的相关问题是找到所有 g(C) 大于阈值的组合。

最佳答案

使用位图对现有组合进行键控,其中位 n 表示 An 是否在该特定编码中。将位图键控的值存储在您最喜欢的散列图结构中。因此,f(A0, A1, A10, A12) 将是 combo_val[11000000001010000...]

要对所有所需的组合求和,请构建根的位图。例如,对于上面的组合,我们将得到 root = 1100000000101000(为了便于说明,总共截断了 16 个元素。

现在使用 root 作为掩码简单地遍历 hashmap 的键。对所需值求和:

total = 0
for key in combo_val.keys()
if root && key == root
total += combo_val[key]

这会让你动起来吗?

关于algorithm - 子集上定义的函数总和,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/57505245/

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com