数学建模社区-数学中国
标题:
分配难题
[打印本页]
作者:
maybe_madio
时间:
2010-10-24 09:28
标题:
分配难题
设有4个盒子，标号为1，2，3，4. 有15个颜色相同的小球, 现在要将15个颜色相同的小球分配到4个盒子中,
& v( o( n9 n1 Z2 C9 X1 Z8 R" L
要求每个盒子至少有一个小球，并且对于盒子中小球的数目，盒子1>盒子2>盒子3>盒子4. 请问一共有多少种分配方法.
0 g/ d7 e% Z6 R6 f6 ?
作者:
fgfroom214
时间:
2010-10-24 09:54
先在每个盒子中放一个小球，就变成11个小球随意放在四个盒子里，这样就变成了一个分折成4个数的加法了
7 I( r. q8 `) {3 J
作者:
maybe_madio
时间:
2010-10-24 10:08
回复
fgfroom214
的帖子
5 Y6 H! @( R( S [) T b7 m
, M! e( a/ _- @: l# C( s* M- B
( ]8 B0 J/ d8 Y7 x4 p
你说的是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
" b6 I" U: M r: m* V9 i1 ]
2、X4=1,剩下14球，三个分，按上面方法，2<= X3 <=3,所以去取X3=2，或3，，，，，
: O8 V, `6 }3 I, u* o6 E9 J
X4 X3 X2 X1
; f9 k i2 K2 _+ P' U9 m# G* ^
1 2 3 9
, U6 }, A! F( z8 A5 [ F! N
4 8
' I4 u0 x+ Q! e+ z% r
5 7
2 B& ?6 c r: t" G9 p
3 4 7
1 Z$ h$ v5 r5 F4 d
5 7
# @. b/ ~3 _7 t/ _& Q
2 3 4 6
9 X& o5 R: _' ^( v: X
作者:
吴宇昊
时间:
2010-10-24 12:24
这个不是排列组合的题目吗？
作者:
1124629740
时间:
2010-10-24 17:53
作者:
1124629740
时间:
2010-10-24 17:53
作者:
cheeryoung
时间:
2010-10-24 19:13
1239
+ a! \; y- w2 E( U; I& l9 W0 x
1248
3 @; K9 E9 b1 z6 \' Y7 W
1257
2 G, |6 K: S' A
1347
4 I1 L9 Q7 {! ~. W) D! j9 u
2346
作者:
1124629740
时间:
2010-10-24 22:18
作者:
guoshaoming
时间:
2010-10-25 00:04
本帖最后由 guoshaoming 于 2010-10-25 00:08 编辑
! d. \1 a! x b% \
5 x8 L; q2 {& a3 i4 a' g4 l0 f
回复
maybe_madio
的帖子
( P0 t) @1 G4 M8 d: O' C
分配方案如下：
9 u4 k- i6 _: F* T$ s: [! Q
6 4 3 2
* s2 R& [$ c! p/ ?$ f- [8 A# A
6 5 3 1
# s$ _6 u) Z9 I/ b5 M
7 4 3 1
% I) q# z0 o6 J9 ?1 J/ L- X
7 5 2 1
2 F' u2 U6 [: }, w
8 4 2 1
8 @! _; x# P0 z( C
9 3 2 1
+ U! K4 |; h0 h; R/ Y4 }
其代码如下：
% {# j0 P/ R# x8 _
#include < iostream >
1 z, M; f0 k1 J f( J5 F
. [7 X8 {6 c4 X8 d9 j
using namespace std;
+ g9 s* |; X' p! w
3 M) ~5 i5 i0 P/ h( A% Q
2 \3 Z9 E) @# _- l6 z$ X
int main()
5 s0 f: `; d! o: t& M
{
2 A9 x2 Y2 m4 s
int x1,x2,x3,x4;
7 S" Y/ j+ Z* B: G4 U
int t=0;
+ O& c( a O2 E1 j" {3 s
0 z" Z: Q- R5 I1 N
for(x1=1;x1<15;x1++)
) [) ~) f3 I" _* ]$ @1 k5 {
for(x2=1;x2<15;x2++)
' e2 [/ d% D6 E1 Y
for(x3=1;x3<15;x3++)
5 `2 u5 v9 w5 k) i/ k
for(x4=1;x4<15;x4++)
# O4 b7 t$ a' R8 e
{
0 V; Q2 M B7 D( {
if((x1+x2+x3+x4==15)&&(x1>x2)&&(x2>x3)&&(x3>x4))
6 b7 x0 q, s, z; l# {3 J! D8 K2 D
cout<<x1<<"\t"<<x2<<"\t"<<x3<<"\t"<<x4<<endl;
9 T4 B- m7 H& c6 h0 z
* l" f* |- C1 t4 m* [ F
}
/ d, x. V) B6 c% V: x2 u% }4 X
return 0;
: m. Q& B1 g- a5 ^9 P3 z
}
* ?6 w. j( i0 S* e5 v7 P2 p
; C0 d0 p6 O* Y3 s3 s$ v
作者:
maybe_madio
时间:
2010-10-25 19:47
回复
guoshaoming
的帖子
3 i( R# G c! p" z! ?5 ?& K8 u
: O: t! M, O# `8 b! G8 F1 ^
, X! O6 L- V3 L, O( V1 i3 a! U
虽然对于15来说，比较容易算出， 那如果我的变量再增多呢？ 假设有x1+x2+..xm=n呢？（m<n）
/ `4 H7 n, V9 M% i( G2 X
能否有更好的程序算法来解决这个问题呢？ 你的穷举算法也只能适用于少量的变量和n较小的特例，当变量增多，或是n变大，这是阶乘级的时间复杂度哦！
- ~) d0 V9 c5 \7 u3 z
作者:
guoshaoming
时间:
2010-10-25 22:52
回复
maybe_madio
的帖子
3 w% o0 m, b3 ]8 g- ?/ w" |4 G
本身这个算法就很具有一般性，如果你增加变量，只要对程序稍加改动就可以了，
( k* `, r* V2 T1 H5 g- |) _
for(xm=1;xm<n;xm++)
2 L' Y" E/ F$ B, M. `# X0 U
然后判断语句和输出也做相应改变
: m& d4 \+ O0 W3 w0 d: K8 F
9 C5 [# L& d& E6 l2 k% I+ u6 m; e( b
作者:
guoshaoming
时间:
2010-10-25 23:17
回复
maybe_madio
的帖子
4 B6 {# _# W' H, Q1 |
当你的变量大到一定程度的时候，你可以将约束条件写成一个循环语句，判断、输出也可以写成相应的循环语句！
6 q2 S( w% r9 n2 r- P
反正程序的总体思路就是上面那个，过多的我就不多说了
" d' D$ j, i$ ]. 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
