数学建模社区-数学中国

标题: 分配难题 [打印本页]
作者: maybe_madio    时间: 2010-10-24 09:28
标题: 分配难题
      设有4个盒子，标号为1，2，3，4.   有15个颜色相同的小球, 现在要将15个颜色相同的小球分配到4个盒子中,
$ c3 A. z& \  N+ w( }' d& I要求每个盒子至少有一个小球，并且对于盒子中小球的数目，盒子1>盒子2>盒子3>盒子4.  请问一共有多少种分配方法.
" Z1 c% M0 B2 G2 X
作者: fgfroom214    时间: 2010-10-24 09:54
先在每个盒子中放一个小球，就变成11个小球随意放在四个盒子里，这样就变成了一个分折成4个数的加法了( c0 d+ J0 ?7 _" m
作者: maybe_madio    时间: 2010-10-24 10:08
回复 fgfroom214 的帖子
; M* D! z; |% ~2 a  b' C7 C) B% ^; C7 Z6 b7 s& i: Z8 k7 S/ v

; \+ v# A0 U- G" N( r. F  Q* y: @    你说的是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! V" V) h* t* f; o0 j
2、X4=1,剩下14球，三个分，按上面方法，2<= X3 <=3,所以去取X3=2，或3，，，，，5 K- C1 y9 g( B9 q% M; C/ ^1 {/ d' |
  X4   X3   X2   X1
( ]1 f) w) u! L  v 1     2     3     9/ `* U; _# [4 n1 Q( X0 ]
               4     8
0 j* [. @' j6 n- N( P               5     7
9 w) D: u4 c) m- t: w$ M4 m       3      4     7: v8 J1 D1 w( T  J6 J6 ~
               5     7
  H: j+ |% O7 r! w7 Q2     3     4     6* q, T9 [: R1 P! v
作者: 吴宇昊    时间: 2010-10-24 12:24
这个不是排列组合的题目吗？
作者: 1124629740    时间: 2010-10-24 17:53
作者: 1124629740    时间: 2010-10-24 17:53
作者: cheeryoung    时间: 2010-10-24 19:13
1239
2 r, U" D3 Q4 }9 H0 {& g1248
3 G/ ^& N  j3 `1257+ l1 T7 \5 P% g1 L
13474 b( x2 ]4 H# k/ ^3 K+ l3 ^
2346
作者: 1124629740    时间: 2010-10-24 22:18
作者: guoshaoming    时间: 2010-10-25 00:04
本帖最后由 guoshaoming 于 2010-10-25 00:08 编辑
& P9 ], g0 e, V; y; M% Q
" ~5 ^) T: @* x; g回复 maybe_madio 的帖子
# L7 |; D5 Q6 Z2 g* x分配方案如下：" W9 u9 _  U$ i9 \$ Y5 F  `
6       4       3       2* S2 ^3 D2 o0 S
6       5       3       1
  s/ K0 i& H: n- v' y' {7       4       3       1
$ U6 n) y' t! @5 [7       5       2       1/ e9 i/ l  v5 C  v. M: L* f
8       4       2       1
7 {) N- Z9 D. e6 ~# X' o/ M9       3       2       18 f8 d/ R9 p* g! m1 F1 F0 Z3 w9 b- ^
其代码如下：
. i: e. n! `- J# c! s#include < iostream >" d' Y5 i* j2 |

" ~8 K6 a0 g3 r9 ~' t  ~using namespace std;
* E0 R6 \3 H" f3 p& B- o0 z: f4 ?: ]" W: ^+ w
" N+ A- w. J5 o! J
int main(). U% O* g6 \9 O* J( s
{
2 k4 |" o" v/ U* t2 `int x1,x2,x3,x4;
+ E, Z) a0 j. t8 |0 `# ?int t=0;7 \) }+ n% {/ E! U9 R& @

/ ?' v$ A* ^% O8 d% D: q9 lfor(x1=1;x1<15;x1++), }6 c; i1 G% _2 x3 G% _8 i  e
for(x2=1;x2<15;x2++)
5 D/ A3 I& L. d2 p* m+ zfor(x3=1;x3<15;x3++)
3 M" }  [$ e$ }0 c7 o+ ?for(x4=1;x4<15;x4++)
2 V! C/ F" |- _: L{( v3 U# i" M2 q2 O* \; i0 y
if((x1+x2+x3+x4==15)&&(x1>x2)&&(x2>x3)&&(x3>x4))
2 N% {+ D: d4 p. ?4 Jcout<<x1<<"\t"<<x2<<"\t"<<x3<<"\t"<<x4<<endl;7 g/ v- x  B% p' g0 X
0 `, p8 N4 e1 Q# V
}
! Y& p* y: \% G" D4 a/ v! Dreturn 0;
! E' J9 ^4 X8 U% _4 j} 7 w" r5 I0 V# m& H2 ?
5 S2 {2 b' ~% x7 A
   
作者: maybe_madio    时间: 2010-10-25 19:47
回复 guoshaoming 的帖子
( D3 ^- \6 h1 s8 n$ M4 y/ E* r4 ]$ y. E& M' _& a  x7 K- F
  I4 b5 }: a% d; F9 }5 ?! ^
    虽然对于15来说，比较容易算出， 那如果我的变量再增多呢？ 假设有x1+x2+..xm=n呢？（m<n）7 s' A: e3 v! l$ F2 ?4 z  ~
能否有更好的程序算法来解决这个问题呢？ 你的穷举算法也只能适用于少量的变量和n较小的特例，当变量增多，或是n变大，这是阶乘级的时间复杂度哦！, h$ e5 `. [' {6 q# @0 o# E9 g
作者: guoshaoming    时间: 2010-10-25 22:52
回复 maybe_madio 的帖子6 U$ H# I* C3 m- {" o5 ]  [+ ^( K
本身这个算法就很具有一般性，如果你增加变量，只要对程序稍加改动就可以了，
4 B- a  F, k) t' A9 F1 Lfor(xm=1;xm<n;xm++)
! e9 y7 t! f# a/ s然后判断语句和输出也做相应改变( U! \: b; J- [& \# M

7 L. C$ ~, d' t* v2 S, K: A   
作者: guoshaoming    时间: 2010-10-25 23:17
回复 maybe_madio 的帖子% S, m9 O; `$ w! @
当你的变量大到一定程度的时候，你可以将约束条件写成一个循环语句，判断、输出也可以写成相应的循环语句！( I# @5 R- b3 R4 U3 L  U; n
反正程序的总体思路就是上面那个，过多的我就不多说了
8 c' F' ]4 X9 _5 C   
作者: 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