固定大小设置为包含给定集的最大数量

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 的价格。（只有当集合中包含的所有数字都已支付时，集合才会支付奖励。）

您可以使用最大流算法解决此类问题：

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

解决该图上的最大流问题（从源节点到目标节点）会找到最小切割成本 c。

我们赚到的净钱是 Nx-c（其中 N 是套数）。

如果我们可以选择 y（例如通过二分），以便我们恰好选择了 20 个数字，那么我们就成功地求解了包含 20 个数字的集合的最大数量。