algorithm - 固定大小的集合包含给定集合的最大数量

Question

我有大约 1000 组大小 <=5，包含数字 1 到 100。

{1}, {4}, {1,3}, {3,5,6}, {4,5,6,7}, {5,25,42,67,100} ... 

是否有可能找到一个大小为 20 的集合，其中包含给定集合的最大数量？

检查每个 100!/(80!*20!) 集合是低效的。

Answer 1

我不太确定这是 NP 完全的。

考虑相关问题，我们为每个集合获得 x 的奖励，但必须为我们想要允许的每个数字支付 y 的价格。 (一组仅在其包含的所有数字都已支付时才支付奖励。)

您可以使用 max flow algorithm 解决此类问题通过:

1. 设置源节点
2. 设置目标节点
3. 为每个集合设置一个节点
4. 为每个数字设置一个节点
5. 将源中的边添加到容量为 x 的每个集合
6. 将每个数字的边添加到容量为 y 的目的地
7. 对于集合s中的每个数字a，添加从s到具有无限容量的a的边

解决此图上的最大流问题(从源节点到目标节点)找到最小切割成本 c。

我们将赚取的净收入为 N.x-c(其中 N 是套数)。

如果我们可以选择 y(例如，通过二分法)使得我们恰好选择了 20 个数字，那么我们就成功地解决了包含 20 个数字的最大集合数。