algorithm - 寻找不相关的元素的最大子集

Question

我有一组整数，我想找到其中元素不以特定方式相互关联的最大子集。例如一个子集，其中如果任何元素乘以 13，则结果不在子集中。

我的第一个想法是遍历所有可能的子集，过滤掉那些不满足条件的，然后找到最大的，但是这样太慢了，我不知道如何生成所有可能的子集。

Answer 1

我会回答这个问题(来自评论)。一般来说，任何“相关性”都没有好的解决方案

Relationship is the following : if you multiple any of the elements in the subset by some number the resulting number does not have to be in the subset.

如果你的号码是m

你可以生成所有的链 x, x*m, x*m*m, ...., 这样所有的数字in chain 都在集合中，x/m 不是

从原始集中删除每隔一个元素，即 x*m^2、x*m^4。剩下的元素是您的目标集。