数学建模社区-数学中国
标题:
分配难题
[打印本页]
作者:
maybe_madio
时间:
2010-10-24 09:28
标题:
分配难题
设有4个盒子，标号为1，2，3，4. 有15个颜色相同的小球, 现在要将15个颜色相同的小球分配到4个盒子中,
1 X8 R4 J4 }0 j# @
要求每个盒子至少有一个小球，并且对于盒子中小球的数目，盒子1>盒子2>盒子3>盒子4. 请问一共有多少种分配方法.
& z9 q5 O3 r/ v8 H9 P- h) \
作者:
fgfroom214
时间:
2010-10-24 09:54
先在每个盒子中放一个小球，就变成11个小球随意放在四个盒子里，这样就变成了一个分折成4个数的加法了
$ }0 ]' s! i3 D) j7 k
作者:
maybe_madio
时间:
2010-10-24 10:08
回复
fgfroom214
的帖子
; O0 Z/ E* r: U Q. d4 j3 u( a
' ~ `. g/ R$ Z5 |1 f1 z
# m) r' s# {5 E$ Y9 i! X/ S9 O
你说的是x1+x2+x3+x4=15, 将每个盒子先放一个后，就转化成x1+x2+x3+x4=11了，再使用C(14, 3)就可以得到所有解了，但是必须要求x1>x2>x3>x4的嘛！ 这样又该怎么建模呢？
作者:
081270053
时间:
2010-10-24 10:45
先放个1234，再分15-10试试？
作者:
081270053
时间:
2010-10-24 10:45
先放个1234，再分15-10试试？
作者:
hhex01
时间:
2010-10-24 11:52
6?
作者:
Baby_Boy
时间:
2010-10-24 12:02
1、首先 1<= X4 <=2 (若X4>2, 3+4+5+6=18>15)； 6<=X1<=9
3 I" g- F6 P% Q: i1 K# B/ a
2、X4=1,剩下14球，三个分，按上面方法，2<= X3 <=3,所以去取X3=2，或3，，，，，
+ C5 x! ?) j: m7 @8 g" K
X4 X3 X2 X1
Q9 G6 o* \' F2 Q' d' @: {# D7 r5 b# T
1 2 3 9
# ?& a4 e* C2 r% W
4 8
# ~* K# R+ s7 ^; P/ |: j
5 7
! h. ?! ?' ]8 ^9 N* }
3 4 7
- G! T+ Z4 f& k9 A2 `* \# ~
5 7
' W( S5 J. U* y5 H0 h
2 3 4 6
2 _. _& O& G; m0 Q
作者:
吴宇昊
时间:
2010-10-24 12:24
这个不是排列组合的题目吗？
作者:
1124629740
时间:
2010-10-24 17:53
作者:
1124629740
时间:
2010-10-24 17:53
作者:
cheeryoung
时间:
2010-10-24 19:13
1239
% W! p2 v9 u' ^3 O& ~. o
1248
0 I& Z& y$ A3 c+ s" t- L
1257
6 b2 c: v8 x9 t6 L- e
1347
: {+ d. g, ]# U* w
2346
作者:
1124629740
时间:
2010-10-24 22:18
作者:
guoshaoming
时间:
2010-10-25 00:04
本帖最后由 guoshaoming 于 2010-10-25 00:08 编辑
1 E3 _3 i4 _- J5 ]
5 I U2 s) }7 p5 |; E3 s4 D0 {
回复
maybe_madio
的帖子
; G0 q9 P4 i( }* D
分配方案如下：
E& v, T& ^& S8 {5 C6 t d7 f! y
6 4 3 2
0 P0 |0 x# h) T6 i% p! H& b
6 5 3 1
2 H8 C X% T$ V- Z
7 4 3 1
. ~3 h/ q- X: G3 N/ o! L
7 5 2 1
8 ?) o" r, w. f* C7 H% o' e; w3 T3 [
8 4 2 1
* M2 X% r% j$ O' f' b1 }
9 3 2 1
% O; ^2 i4 O+ u4 X+ F3 N [
其代码如下：
) _$ j1 N- ^' d; C: y, b
#include < iostream >
( l9 S i8 ?4 e
; `6 R8 G2 ?) |: E1 K% J; S
using namespace std;
( d3 n; `. j+ D( J% u) v% l- k
& |% v1 p5 c9 z7 h3 k2 C
+ `) l; Q' f3 q3 ?* ^4 V
int main()
. }, z) n! M2 s* b5 N+ b) q0 c
{
- w0 }1 r" l& n% ]) i
int x1,x2,x3,x4;
1 w! Z& y; U- c: _: a/ t8 O
int t=0;
: R- }/ v: V3 _) m1 _
/ X! {, e2 {: q; h
for(x1=1;x1<15;x1++)
/ J! q0 Y9 A8 z# U* p" w
for(x2=1;x2<15;x2++)
2 x$ l3 H7 h2 O, ^ G6 w8 e F
for(x3=1;x3<15;x3++)
7 c3 Z4 |+ ^6 w- ^
for(x4=1;x4<15;x4++)
% S6 o" j# K- ^7 ^+ i
{
: L! K- m* e$ m8 _/ p! B1 C r. v' r7 g
if((x1+x2+x3+x4==15)&&(x1>x2)&&(x2>x3)&&(x3>x4))
) m9 L; K/ c. E) o$ D
cout<<x1<<"\t"<<x2<<"\t"<<x3<<"\t"<<x4<<endl;
2 c% B! u! l: `3 J, ~
: r% i" a+ T$ x
}
+ r1 U. |/ d, N4 F
return 0;
! `! v) D6 q' j B
}
# {; V. H+ O! R7 u) L
# Z5 Y- q8 ?$ H* N% N8 H
作者:
maybe_madio
时间:
2010-10-25 19:47
回复
guoshaoming
的帖子
2 C: u! c; Q2 b+ f7 ~$ ~( x, e
0 O! W/ a5 G3 _" L4 V
) |$ F; b# ?8 V* H6 ^* X; v/ k8 ]9 w
虽然对于15来说，比较容易算出， 那如果我的变量再增多呢？ 假设有x1+x2+..xm=n呢？（m<n）
6 K3 J) Q4 P1 k" b
能否有更好的程序算法来解决这个问题呢？ 你的穷举算法也只能适用于少量的变量和n较小的特例，当变量增多，或是n变大，这是阶乘级的时间复杂度哦！
* @ K$ E/ i- p8 j9 w
作者:
guoshaoming
时间:
2010-10-25 22:52
回复
maybe_madio
的帖子
# r0 K+ y/ D* {: _. @: z
本身这个算法就很具有一般性，如果你增加变量，只要对程序稍加改动就可以了，
: u. o( c" c/ F- Z1 ]& q
for(xm=1;xm<n;xm++)
1 O# \9 i6 k; `6 M. H6 Q# o
然后判断语句和输出也做相应改变
8 ^8 k) E! g4 Z6 O
3 `3 m5 i4 c3 E) J
作者:
guoshaoming
时间:
2010-10-25 23:17
回复
maybe_madio
的帖子
1 h) D; d# Z0 Y; Z$ w0 r
当你的变量大到一定程度的时候，你可以将约束条件写成一个循环语句，判断、输出也可以写成相应的循环语句！
! }0 Q0 n+ c8 j3 @/ r
反正程序的总体思路就是上面那个，过多的我就不多说了
% R. d4 y$ J; [* P" m, b- P7 i
作者:
linmatsas
时间:
2010-10-25 23:21
要是好多好多球好多好多盒子可怎么办呢…………这真是一个问题呀………………不过一时想不出来其他算法了……应该穷举能做呀…………应该用不了几个小时吧…………
作者:
whui
时间:
2012-1-1 15:54
13种呀。。。。。。。。。。。。。。。。
作者:
whui
时间:
2012-1-1 18:35
13种。。。。。。。。。。。。。
作者:
漂流者
时间:
2012-1-5 18:29
可以先把15个球排成一排，然后从他们之间的14个间隔里插入3块板，就可以把15个小球分成4份了，用这个思想，可以很容易解决你的问题，隔板法是很经典的东西。
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5
