数学建模社区-数学中国

标题: 请教各位大神一个组合数学的问题 [打印本页]
作者: mathm0del    时间: 2015-10-21 15:12
标题: 请教各位大神一个组合数学的问题
请教各位大神一个组合数学的问题：
) A1 V" P; O: d4 j  e1 B) [0 |
( e$ x) b* N9 l+ u4 I1：在m个样本中(45<=m<=54)，随机选出n个样本(7<=n<=25)。从刚才这n个样本中，再随机选出k个样本(4<=k<=7)组成一些组合，那么这些组合有S1(也就是C(n,k))个。再从n个样本中选出s个样本(3<=s<=7)，这样就有S2（也就是C(n,s)）个组合。4 A7 c% k1 \5 P$ I& w6 ~8 d
3 F! F" J8 Y2 H9 W
2：我们知道，S1的组合当中，某些组合中的元素，覆盖了S2的组合当中某一个或者某几个组合的所有元素。
2 o* `) D; R4 h0 a; @; K例如：S1的组合当中有一个组合是a1（a,b,c,d,e）,S2的组合当中有一个组合是b1(b,d,e)，另一个组合是b2(a,c,d)。那么a1中的元素就覆盖了b2，b3中的所有元素，这样相当于覆盖了两个S2中的组合。9 V5 Z1 L) }% @$ P& v! y9 D" y  f, W

8 ]6 q" _: K" Q: P3 P现在，要求S1的组合当中最少要有多少个像a1这样的组合，就能覆盖S2中的所有元素。并列出这些组合。2 u3 {# j* E1 r; ~) ]+ h1 k( h

, e4 r' y& ?" {1 F' t, r% |" G举例：
% {# {& P1 D3 d! B3 a+ W假设从m=45个样本中，随机抽取n=7个样本（假设这些样本是A,B,C,D,E,F,G），k=6，s=5，那么S1=C(7,6)=7，S2=C(7,5)=21。在S1当中，只需要最少如下6个组合，就可以覆盖S2中组成所有组合的元素。4 k) P) x+ S9 O

  v/ P- i$ V+ n* W2 x1. A,B,C,D,E,G  2. A,B,C,D,F,G  3. A,B,C,E,F,G
9 o% W& S# @0 s2 ?) _7 U4. A,B,D,E,F,G  5. A,C,D,E,F,G  6. B,C,D,E,F,G
1 Q( O- c9 z! j- [
/ u4 h0 ^/ b1 R$ Z
. r. j8 F- S0 Z- V9 T! ^* y2 F- k4 }小弟想知道怎么编程解决这个问题？或者有没有什么数学方法，能直接找出这些最小的组合？
7 N, o! m0 G# [: A* g9 N" G: T( s. v% I0 w- [
原题是英文的，如附件：
5 r) [0 l: d* z3 ~( Z) v! l 英语原文.pdf (283.04 KB, 下载次数: 1) 4 m. q: Y0 h$ c! A  e+ u1 R
3 t: y) `# ]. Z6 v" l
, I- Z: V% M7 f7 i7 @

8 k. \# P/ r3 t
: C, G; I! J. ^: D



欢迎光临 数学建模社区-数学中国 (http://www.madio.net/) Powered by Discuz! X2.5