固定尺寸设置为包含给定集的最大数目 [英] Fixed size set to contain the maximum number of given sets

问题描述

我有大约1000套的大小和其中的= 5包含数字1到100

I have about 1000 sets of size <=5 containing numbers 1 to 100.

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

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

Is it possible to find a set of size 20 that contains the maximum number of given sets?

检查每个 100！/（80！* 20！）套，效率不高。

Checking each of 100!/(80!*20!) sets, is inefficient.

推荐答案

我不敢肯定这是NP完全性。

I am not so sure this is NP complete.

考虑相关的问题，我们得到x对于每一集的报酬，但必须支付y的价格，我们希望让每一个号码。 （一组只需要支付的奖励，如果它包含所有已支付的数字。）

Consider the related problem where we get a reward of x for each set, but have to pay a price of y for each number that we want to allow. (A set only pays the reward if all the numbers it contains have been paid for.)

您可以使用最大流算法通过解决这一类型的问题：

You can solve this type of problem using the max flow algorithm by:

1. 设置一个源节点
2. 设置一个目的地节点
3. 设置一个节点的每个组
4. 设置一个节点的每个号码
5. 从源添加边缘到每一组容量X
6. 添加边从每个数字到dest容量是
7. 对于集合S每一个数字，加上从s边缘到一个具有无限容量

解决这个图中的最大流问题（从源到目的节点），找到一个最小割的费用C。

Solving the maximum flow problem on this graph (from the source to destination node) finds a minimum cut cost c.

净额的资金，我们将做出将NX-C（其中N是数台）。

The net amount of money we would make would be N.x-c (where N is the number of sets).

如果我们可以选择y（按二分法EG），使得我们选择了整整20号，我们已经成功地解决了套有20个数字的最大数量。

If we can choose y (e.g. by bisection) such that we have selected exactly 20 numbers, then we have managed to solve for the maximum number of sets with 20 numbers.

这篇关于固定尺寸设置为包含给定集的最大数目的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！