最少数目最大覆盖的问题，请高手指点！！分不够还可以继续加！ ( 积分: 300 )

问题：
有n个不同的数，记为D1, D2, ...., Dn
以及由这n个数中提取4个不同的数形成的各不相同的m个组合(组合是要满足一定条件的，不是n个数的完全组合)，记为：
(P11, P12, P13, P14)
(P21, P22, P23, P24)
......
(Pm1, Pm2, Pm3, Pm4)
其中的每一个元素Pij都是属于n个数D1,..., Dn中的一个。
删除操作：n个数D1, ..., Dn中，删除一个数Dk，那么就要同时删除m个组合中每一个包含Dk这个数的组合。
例子：假如要删除D1，而P23=D1，那么就同时删除第2个组合。这样,可能删除了若干个数(小于n)及其相应的组合,就把所有的组合全部删除掉了。
问题是：对这n个数，采用什么样的删除顺序，可以达到这样的目的：删除最少的数，就能把所有的组合全部删除？（最少数目最大覆盖）
我曾经实现过的思路是：统计m个组合中出现的每一个数的次数，从出现次数高的开始删起，但是结果证明，这样的方法不是最优的，就是说比手算得到的结果少，多删了几个数。
困惑了好几天了，头都想痛了，还没有一个思路。敬请算法高手或者数学高人指点迷津！！
分不够可以继续加！！！
跟贴者有分！！！(将另开贴)

就上学的时候学过数据结构，现在全忘记了，帮楼主顶一下吧。

唉!
大学的数学分析就是难!
呵呵!

敢问LZ这题目是哪来的?
我觉得D1, D2, ...., Dn 这n个数在组合中的分布是平均的,
所以这问题就变成了
得到 每个数在组合中所覆盖的数量(这数量当然由n决定)
和 n个数的组合的总数量是多少
那个大于后者除以前者的最小整数就是你要的答案了(是一个含有n的表达式)

经过初步研究,得到以下结论:
从m个数中取不重复的n个数组成内容不重复的组合时,
n!
其组合的总数量为 ----------
m!*(n-m)!
而其中每个数在组合的总数中出现的次数为
n! (n-1)!
---------- - -----------
m!*(n-m)! m!(n-m-1)!
最小删除数就是大于
n! n! (n-1)!
(-----------)/( ---------- - ----------- )
m!*(n-m)! m!*(n-m)! m!(n-m-1)!
这个表达式的最小整数
只是初步研究,有不对的地方可以再讨论(不摸数学好多年了)

至于程序算法嘛!自己用5,6,7,8试下就知道规律了
基本规律 1 1,2 1,2,3 1,2,3,4 1,2,3,4,5
可以在Delphi中随便用2个嵌套循环就可以根据输入的m,n的值算出最小删除数了.

感谢lynch2611的支持！
不过你可能没有注意到，上面有一句话：
组合是要满足一定条件的，不是n个数的完全组合
所以这里的m个组合，m <> n!/(4!*(n-4)!), 也就是说m可能会远小于从n个数中取4个数的所有组合的数目，D1,..., Dn在m个组合中出现的次数一般也不是均匀的。

错!
1 以上公式在 0<m<=n时都成立!
2 D1,..., Dn中每个数在m个组合的总数中占的比例是一样的(可以用我上面的公式计算)
建议你用点简单的数字自己看看 验证后就知道我的公式是正确的了(我自己用5,6,7,8试过)
你可以验证下,如有反例,说出来,我们再研究下

高深的问题，顶一下，新手

好!

例子：
D = (80, 81, 82, 83, 84, 85, 86)
共有51个组合(抱歉，以前没有说的很明白，实际上有些组合整理后，只剩余3个数，但是相信不会产生实质影响)
1: ( 81 , 82 , 83)
2: ( 81 , 82 , 80)
3: ( 80 , 82 , 84)
4: ( 80 , 81 , 82 , 83)
5: ( 80 , 81 , 82)
6: ( 81 , 83 , 85)
7: ( 80 , 83 , 86)
8: ( 80 , 81 , 83 , 84)
9: ( 80 , 81 , 84 , 85)
10: ( 80 , 81 , 85 , 86)
11: ( 80 , 81 , 86 , 85)
12: ( 82 , 83 , 84)
13: ( 82 , 83 , 81)
14: ( 80 , 82 , 83 , 85)
15: ( 82 , 84 , 86)
16: ( 82 , 84 , 80)
17: ( 80 , 82 , 84 , 86)
18: ( 80 , 82 , 85 , 83)
19: ( 80 , 82 , 86 , 84)
20: ( 83 , 84 , 85)
21: ( 83 , 84 , 82)
22: ( 80 , 83 , 84 , 81)
23: ( 83 , 85 , 81)
24: ( 80 , 83 , 85 , 82)
25: ( 83 , 86 , 80)
26: ( 84 , 85 , 86)
27: ( 84 , 85 , 83)
28: ( 80 , 84 , 85 , 81)
29: ( 84 , 86 , 82)
30: ( 80 , 84 , 86 , 82)
31: ( 85 , 86 , 84)
32: ( 80 , 85 , 86 , 81)
33: ( 81 , 82 , 83 , 80)
34: ( 81 , 82 , 84 , 85)
35: ( 81 , 82 , 85 , 86)
36: ( 81 , 82 , 86 , 85)
37: ( 81 , 83 , 84 , 80)
38: ( 81 , 83 , 86 , 84)
39: ( 81 , 84 , 85 , 80)
40: ( 81 , 84 , 86 , 83)
41: ( 81 , 85 , 86 , 80)
42: ( 82 , 83 , 84 , 81)
43: ( 82 , 83 , 85 , 80)
44: ( 82 , 83 , 86 , 85)
45: ( 82 , 84 , 85 , 81)
46: ( 82 , 84 , 86 , 80)
47: ( 82 , 85 , 86 , 81)
48: ( 83 , 84 , 85 , 82)
49: ( 83 , 84 , 86 , 81)
50: ( 83 , 85 , 86 , 82)
51: ( 84 , 85 , 86 , 83)
上面的最优结果是：
删除三个数：82, 83, 85
最后剩余： 80, 81, 84, 86
但是按照我的思路删除下来，只剩余80，85，86。
lynch2611的方法感觉还不对思路。因为他是基于组合是有规律可循来考虑的。假如不要考虑标准的组合个数公式，而只是从已经存在的组合来考虑，这样才行。

跟进学习中.新手[8D]

如此try一把
把所有选出来的集合如此重新写
D = (80, 81, 82, 83, 84, 85, 86)
1: ( x, 81, 82, 83, x, x, x)
2: ( 80, 81, 82, x, x, x, x)
3: ( 80, x, 82, 83, 84, x, x)
然后排序，并可以剔除重复的，因为按照题意，和集合内部的次序无关，在解题过程中可以排除他的额外影响。
然后第二步是以每列为基准算一个重要的参数，并记录下来，即每列相对于其他列的重合度，或者称为他们的关系，这些关系无外乎 A列包含B列，A列和B列无交叉，A列和B列交叉等等。而他们的含义就是，如果A列包含B列，那么说明删除了A就删除了B，如果A列和B列无交叉部分，那么说明删除A列绝对不会删除B列，如果A列和B列有部分交叉重合，则说明删除A会同时删除B列的若干个点，
如此，事实上，这样的一个题就变成了一个集合求最小交叉并集的问题。
但因为其中牵涉了N个集合求互相关系的算法，如果D序列数字很庞大，此题难以解答。还是求近似答案未妙。

因为和删除次序敏感，所以很有可能会最后等价到最短路径问题上，如果真是如此，此题就比较麻烦了

这样算可以得到你要的答案，不过我估计这样做得到答案的有一定偶然性。

1: ( 81 , 82 , 83) => ( 81 , 82 , 83) 一个括号内的为可能值，
2: ( 81 , 82 , 80) => ( 81 , 82 )
3: ( 80 , 82 , 84) => ((82)) 二个括号内的为必然值
4: ( 80 , 81 , 82 , 83) => ((82)) 一旦序列中存在必然值则该略过
5: ( 80 , 81 , 82) => ((82))
6: ( 81 , 83 , 85) => ((82), 81, 83, 85) 和必然值序列不重合，加入可能值序列
7: ( 80 , 83 , 86) => ((82),(83)) 确定了第二个必然值。
8: ( 80 , 81 , 83 , 84) => ((82),(83))
9: ( 80 , 81 , 84 , 85) => ((82),(83), 80 , 81 , 84 , 85)
10: ( 80 , 81 , 85 , 86) => ((82),(83), 80 , 81 , 85)
11: ( 80 , 81 , 86 , 85) => ((82),(83), 80 , 81 , 85)
12: ( 82 , 83 , 84) => ((82),(83), 80 , 81 , 85)
13: ( 82 , 83 , 81) => ((82),(83), 80 , 81 , 85)
14: ( 80 , 82 , 83 , 85) => ((82),(83), 80 , 81 ,85)
15: ( 82 , 84 , 86) => ((82),(83), 80 , 81 ,85)
16: ( 82 , 84 , 80) => ((82),(83), 80 , 81 ,85)
17: ( 80 , 82 , 84 , 86) => ((82),(83), 80 , 81 ,85)
18: ( 80 , 82 , 85 , 83) => ((82),(83), 80 , 81 ,85)
19: ( 80 , 82 , 86 , 84) => ((82),(83), 80 , 81 ,85)
20: ( 83 , 84 , 85) => ((82),(83), 80 , 81 ,85)
21: ( 83 , 84 , 82) => ((82),(83), 80 , 81 ,85)
22: ( 80 , 83 , 84 , 81) => ((82),(83), 80 , 81 ,85)
23: ( 83 , 85 , 81) => ((82),(83), 80 , 81 ,85)
24: ( 80 , 83 , 85 , 82) => ((82),(83), 80 , 81 ,85)
25: ( 83 , 86 , 80) => ((82),(83), 80 , 81 ,85)
26: ( 84 , 85 , 86) => ((82),(83),(85)) 上面都被必然值忽略，这里只有一个值呈现可能值，成为必然值
27: ( 84 , 85 , 83) => ((82),(83),(85))
28: ( 80 , 84 , 85 , 81) => ((82),(83),(85))
29: ( 84 , 86 , 82) => ((82),(83),(85))
30: ( 80 , 84 , 86 , 82) => ((82),(83),(85))
31: ( 85 , 86 , 84) => ((82),(83),(85))
32: ( 80 , 85 , 86 , 81) => ((82),(83),(85))
33: ( 81 , 82 , 83 , 80) => ((82),(83),(85))
34: ( 81 , 82 , 84 , 85) => ((82),(83),(85))
35: ( 81 , 82 , 85 , 86) => ((82),(83),(85))
36: ( 81 , 82 , 86 , 85) => ((82),(83),(85))
37: ( 81 , 83 , 84 , 80) => ((82),(83),(85))
38: ( 81 , 83 , 86 , 84) => ((82),(83),(85))
39: ( 81 , 84 , 85 , 80) => ((82),(83),(85))
40: ( 81 , 84 , 86 , 83) => ((82),(83),(85))
41: ( 81 , 85 , 86 , 80) => ((82),(83),(85))
42: ( 82 , 83 , 84 , 81) => ((82),(83),(85))
43: ( 82 , 83 , 85 , 80) => ((82),(83),(85))
44: ( 82 , 83 , 86 , 85) => ((82),(83),(85))
45: ( 82 , 84 , 85 , 81) => ((82),(83),(85))
46: ( 82 , 84 , 86 , 80) => ((82),(83),(85))
47: ( 82 , 85 , 86 , 81) => ((82),(83),(85))
48: ( 83 , 84 , 85 , 82) => ((82),(83),(85))
49: ( 83 , 84 , 86 , 81) => ((82),(83),(85))
50: ( 83 , 85 , 86 , 82) => ((82),(83),(85))
51: ( 84 , 85 , 86 , 83) => ((82),(83),(85))
这样只要整序列过滤一次就完成任务了。比算交集的做法要少计算很多量。
基本规则是，如果当前这个序列中不存在必然值序列，那么把所有的当前值序列充当成可能值序列，如果此时已经有可能值序列，则应和原可能值序列做并集。如果当前值序列中有任何一个值包含在必然值序列中的任何一个值，该序列完全忽略。如果合并后的可能值序列只有一个，那么自动成为必然值序列。

你问题中写的
&quot;...由这n个数中提取4个不同的数形成的各不相同的m个组合...&quot;
是说组合集中每个组合都有4个不同的数吗?

意思是说一个组合中，不存在相同的数。比如不存在(80, 80, 83, 86)这样的组合。
现在，一个组合中可能有3个数，也可能有4个数。

谢谢大家的参与！
不过根据我自己的研究经过，发现结论是：除了从最小数目的组合开始，穷举n个数的所有组合，来检验他们是不是能够完全覆盖给定的m个组合外，应该没有别的办法来找出最优的删除路径。
(如果您认为还有别的更有效的方法，并且实际检验过的，可以给我留言，我们愿意付现金酬金来获得您的研究成果，至少上千元:>)
但是，我还是要说：
Soul果然是高人，我的敬佩之情真的是犹如那滔滔江水，连绵不绝！首先，他指出了这个问题的一般做法，而且指出对于D的元素很多时基本无法求解(不是无解)；其次，第二贴能够提出这样的奇妙思路，虽然不幸被他自己所言中：这样做得到答案的有一定偶然性(可以把8，9两行的组合放到第一行前面，就可以验证了；而且这样的方法，在得出一个必然值时，仅仅依赖于它是局部最优的判断，那么错误就再所难免了)。最重要的是，能够在这么晚的时间还能潜心钻研难题的精神，我辈是做不到的了。
也同时感谢lynch2611，您是一位我很想结识的高人。
也感谢其他几位朋友的参与！

可以改进一下的。有几个点可以改进，
1、如果该数据系列不是流的话，那么可以先做个排序，这样可以消除掉一些随机性。
2、在每碰到一个必然值后，将这个必然值取反序列，变成必然不存在这个值，以此充当可能值同时运算（除非你存在只有一个值的集合，这个假设就有问题了），这样，即便8，9放到前面，得到必然值是81，81去补集可能值进行运算后，依然可以得到82这个必然值，再下去是一样的。每碰到一个必然值产生两个分支。按照可能遇到4个必然值来看，可能产生16个分支，不过因为有些分支可以提前放弃，必然，其他分支还只有3个值，他已经4个值了，那么这个分支可以暂时提前放弃，最后以最后一个最优分支为答案。
这样虽然依然会牵涉到多分支的问题，但远远要比标准做法少得多得多，因为实际上由于这个集合很大程度上对你问题是有冗余信息的。