数学建模社区-数学中国
标题:
分配难题
[打印本页]
作者:
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% ^; C
7 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 Q
2 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 {& g
1248
3 G/ ^& N j3 `
1257
+ l1 T7 \5 P% g1 L
1347
4 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/ M
9 3 2 1
8 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- o
0 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 l
for(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+ z
for(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 J
cout<<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! D
return 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 L
for(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