数学建模社区-数学中国
标题:
请教各位大神一个组合数学的问题
[打印本页]
作者:
mathm0del
时间:
2015-10-21 15:12
标题:
请教各位大神一个组合数学的问题
请教各位大神一个组合数学的问题：
) V( X7 p x# p+ I2 M0 Y
7 @# `0 b _: h4 ^% j0 b5 O) }
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)）个组合。
8 A: D5 R2 r3 |9 S6 I
2 I4 z, u Z( B8 K
2：我们知道，S1的组合当中，某些组合中的元素，覆盖了S2的组合当中某一个或者某几个组合的所有元素。
; L! |( V2 T8 P' n* g7 c( j
例如：S1的组合当中有一个组合是a1（a,b,c,d,e）,S2的组合当中有一个组合是b1(b,d,e)，另一个组合是b2(a,c,d)。那么a1中的元素就覆盖了b2，b3中的所有元素，这样相当于覆盖了两个S2中的组合。
. O5 @- G* }2 O4 ?9 r8 K; _
9 m9 K: n" t& M* ^. H* f0 Z
现在，要求S1的组合当中最少要有多少个像a1这样的组合，就能覆盖S2中的所有元素。并列出这些组合。
: \7 v. A3 c! A
& x- z1 ^* f5 N3 K% s$ o; {
举例：
: q+ k9 F6 Y U6 u' T+ }
假设从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 W0 ^) E' A/ O! D4 Y
) Y( v* `% U, A6 V+ C
1. A,B,C,D,E,G 2. A,B,C,D,F,G 3. A,B,C,E,F,G
9 F3 Y3 q% Y, ?
4. A,B,D,E,F,G 5. A,C,D,E,F,G 6. B,C,D,E,F,G
8 Q# |2 V) U5 P, E* g) P$ Z
3 r& x9 x7 I0 R6 C3 F3 r
- j8 v3 v. x& _# S( \! s
小弟想知道怎么编程解决这个问题？或者有没有什么数学方法，能直接找出这些最小的组合？
1 k! _+ t1 @" A0 g$ ^- B, ?
. @0 ^6 |% ^0 y) K( [
原题是英文的，如附件：
" [( p2 Q' {+ Y+ t& J
英语原文.pdf
(283.04 KB, 下载次数: 1)
2015-10-21 15:12 上传
点击文件名下载附件
下载积分: 体力 -2 点
0 h* F' q7 s7 H9 p
3 W0 m6 k+ a3 c" T$ o
# b! C$ O) w: U0 s) _7 O
, {, T0 k+ r5 Q. \
# \! c' ?6 ~& ?$ d) l' t9 n4 I
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5
英语原文.pdf
(283.04 KB, 下载次数: 1)
英语原文.pdf
(283.04 KB, 下载次数: 1)