请教各位大神一个组合数学的问题: - G) T' Z& g" j; \4 Q, f' J+ b' j7 O* N% ]) B, y
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))个组合。3 G. f' Y5 W8 @' r" A
- f" ~7 q2 ?! r. c, t. Y2:我们知道,S1的组合当中,某些组合中的元素,覆盖了S2的组合当中某一个或者某几个组合的所有元素。+ Z& p$ e& ]9 u* O1 X
例如:S1的组合当中有一个组合是a1(a,b,c,d,e),S2的组合当中有一个组合是b1(b,d,e),另一个组合是b2(a,c,d)。那么a1中的元素就覆盖了b2,b3中的所有元素,这样相当于覆盖了两个S2中的组合。7 k1 L" D# ]. [/ t: O' h
0 W1 J8 Z5 _+ [. X" I$ e6 N
现在,要求S1的组合当中最少要有多少个像a1这样的组合,就能覆盖S2中的所有元素。并列出这些组合。9 f9 X. I0 Q( U1 a# s8 n- Z1 i
/ y! h4 P2 k) }$ {4 H ~
举例:( K- z1 D2 [3 D8 ], 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中组成所有组合的元素。) a! e! }- h$ G6 ^$ ?9 ]
! {* }6 O* P7 X, s5 x5 y; p1. A,B,C,D,E,G 2. A,B,C,D,F,G 3. A,B,C,E,F,G ; S F. d6 k# e [* `* ?( _' K) ^4. A,B,D,E,F,G 5. A,C,D,E,F,G 6. B,C,D,E,F,G : V/ O( U' e# ?: E7 |6 |) q/ ~& L* h$ @. F2 x
* V0 U% t! k0 I0 f! q
小弟想知道怎么编程解决这个问题?或者有没有什么数学方法,能直接找出这些最小的组合? % E1 g7 n ?, n( n( C. p 1 k+ ]; R7 f6 t8 j' k原题是英文的,如附件: # N& y4 ]4 g; {4 J: i0 \$ E. C) P英语原文.pdf(283.04 KB, 下载次数: 1)