数学建模社区-数学中国

标题: 请教各位大神一个组合数学的问题 [打印本页]
作者: mathm0del    时间: 2015-10-21 15:12
标题: 请教各位大神一个组合数学的问题
请教各位大神一个组合数学的问题：
+ P4 P. N8 F% H+ j8 a0 ]. A( j5 W* H! b% H# X6 i% R
1：在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)）个组合。. F# N2 J- }9 @$ r  c6 @. }

6 p* f0 |( s( u* q! o+ D1 j0 d2：我们知道，S1的组合当中，某些组合中的元素，覆盖了S2的组合当中某一个或者某几个组合的所有元素。
1 k( c6 M% K5 n6 j; P8 f- _8 |例如：S1的组合当中有一个组合是a1（a,b,c,d,e）,S2的组合当中有一个组合是b1(b,d,e)，另一个组合是b2(a,c,d)。那么a1中的元素就覆盖了b2，b3中的所有元素，这样相当于覆盖了两个S2中的组合。' D4 P4 S5 ~- K( U& f2 p: ~" K8 u* P3 r8 r
& i& o! g0 ~  c
现在，要求S1的组合当中最少要有多少个像a1这样的组合，就能覆盖S2中的所有元素。并列出这些组合。: t' \% Q4 g7 u5 l( l

" ?; u2 a( G/ D  E: U5 l3 @举例：
) Y% i- h1 M: z+ i- u6 Q. S假设从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中组成所有组合的元素。$ S8 ]1 |3 @! Q7 s' ^- @$ ?( d1 |
- G! |: b. S9 Q; c& s9 X
1. A,B,C,D,E,G  2. A,B,C,D,F,G  3. A,B,C,E,F,G6 y% t! i7 a, @2 M  i* u( U: X
4. A,B,D,E,F,G  5. A,C,D,E,F,G  6. B,C,D,E,F,G+ Y: f9 U5 C0 b
9 u: w7 o/ x. Y# z3 _; E* E
* F) T' E! z, I
小弟想知道怎么编程解决这个问题？或者有没有什么数学方法，能直接找出这些最小的组合？
4 d: ^9 u6 {/ w; t- B1 n6 t2 H; y+ L# Z) l/ }/ \6 @) |
原题是英文的，如附件：
, O; R& O6 ^; T. Y 英语原文.pdf (283.04 KB, 下载次数: 1) ( I+ _  L/ z% A' I$ h- E4 G* S9 z
. H" p* T5 c) a. W. t7 t

. N/ _7 T8 u" S9 \; x0 }" M7 j+ f" h
: p0 U! i2 G* i4 N1 E0 }3 d9 `* Y




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