数学建模社区-数学中国
标题:
分配难题
[打印本页]
作者:
maybe_madio
时间:
2010-10-24 09:28
标题:
分配难题
设有4个盒子，标号为1，2，3，4. 有15个颜色相同的小球, 现在要将15个颜色相同的小球分配到4个盒子中,
+ V. J8 D$ b, B5 x* }4 J: n1 P( U: m
要求每个盒子至少有一个小球，并且对于盒子中小球的数目，盒子1>盒子2>盒子3>盒子4. 请问一共有多少种分配方法.
W( v8 C; @. Q% r; o; h0 }9 h J
作者:
fgfroom214
时间:
2010-10-24 09:54
先在每个盒子中放一个小球，就变成11个小球随意放在四个盒子里，这样就变成了一个分折成4个数的加法了
' _1 q$ j, B( ~; t
作者:
maybe_madio
时间:
2010-10-24 10:08
回复
fgfroom214
的帖子
\" D$ ?; a9 E
2 U K1 @( x' A: B6 B
2 y7 |" q) q. [' x8 {+ \6 h; N" C
你说的是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
4 y$ ~+ s6 j' V+ x3 [+ V+ b
2、X4=1,剩下14球，三个分，按上面方法，2<= X3 <=3,所以去取X3=2，或3，，，，，
! J; h5 f7 ^3 @4 J# ^$ p1 \
X4 X3 X2 X1
! @" B5 N4 T) ]6 S- ^5 {% m/ I# {
1 2 3 9
2 s$ p; @$ \* Z3 w+ m, w
4 8
8 ^0 I( Q' o4 Q2 I* J
5 7
* b& Z% g$ W% Q [, K
3 4 7
9 U5 s* n" ^5 x4 ?! {) a; |
5 7
! ~% Z/ r9 t; h! x
2 3 4 6
5 J+ N/ m' w ~! 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
* w f8 @7 p* a1 o! X5 K8 n3 f
1248
% n, Y, i/ o% s# U. \
1257
- H/ s* ^, Q @, U( i. }, n6 b3 d
1347
$ p# b+ l, T% S/ F, @8 F
2346
作者:
1124629740
时间:
2010-10-24 22:18
作者:
guoshaoming
时间:
2010-10-25 00:04
本帖最后由 guoshaoming 于 2010-10-25 00:08 编辑
3 y) u+ b! t+ S; `
; C) Q; o4 f2 s
回复
maybe_madio
的帖子
+ f' E' j% ^, a! c" A1 r
分配方案如下：
8 |& N9 i/ f. y* W- K" m
6 4 3 2
' e7 s+ e& { S' F9 ?3 H4 ?
6 5 3 1
! u8 [2 n6 V5 r4 G
7 4 3 1
1 ]- V1 e0 Y. c: k8 `, f. L3 x) m
7 5 2 1
: v4 a% O6 F$ J* A1 F
8 4 2 1
# L- e8 L* H# {) |0 O: T1 K1 c- B
9 3 2 1
( H" ]: b+ [- X, @) f* a+ x
其代码如下：
! D. ]3 {" s1 V) B/ ?
#include < iostream >
, \& V* Y% `' E- a- C
3 Y1 X6 m7 k$ V" N4 m% U& e
using namespace std;
0 @5 ]- {/ z/ w! x/ K8 O0 k& R* y
" d. s; v6 S1 l
; _& Q( K, Q, J' M$ A6 k
int main()
, Y3 L- l* Y$ A5 ^2 Y& S1 i o
{
8 r" ]5 |. `5 ]+ V5 i+ {
int x1,x2,x3,x4;
% t# x" N9 C7 a1 X
int t=0;
5 v- V! w! x P# I: b) W
# P5 e# R4 ~$ y0 A, A+ V/ D$ T
for(x1=1;x1<15;x1++)
! ]1 X3 U1 Z, X" L* ]" v
for(x2=1;x2<15;x2++)
' f2 s) ]4 @( M& M7 n; D7 S9 K$ a
for(x3=1;x3<15;x3++)
, d2 g; L# ^' [6 }3 {
for(x4=1;x4<15;x4++)
9 d! y+ x" f3 U" W; a
{
8 t" I- J; B; L( m3 T. _. a
if((x1+x2+x3+x4==15)&&(x1>x2)&&(x2>x3)&&(x3>x4))
0 g3 ]( i2 x. o T
cout<<x1<<"\t"<<x2<<"\t"<<x3<<"\t"<<x4<<endl;
/ ^" U/ a& m; q. J! H# D4 a
" N! E' G* i& J7 ~8 \7 u9 c
}
* G) g8 \" _2 L# K
return 0;
! {: `) a8 [. y, Y
}
) W$ v/ A. n2 L, V, R
$ |) Y6 n! n0 }5 Y5 D5 n3 {
作者:
maybe_madio
时间:
2010-10-25 19:47
回复
guoshaoming
的帖子
" ]8 ^3 H2 R. N: y# I. w% X0 G
; ]7 B9 e% }# u3 B+ E5 ~) ?7 Q
# Y. e* C) x$ ?3 @# H1 ^
虽然对于15来说，比较容易算出， 那如果我的变量再增多呢？ 假设有x1+x2+..xm=n呢？（m<n）
' T$ l* n; ]+ x/ d Y' _5 e
能否有更好的程序算法来解决这个问题呢？ 你的穷举算法也只能适用于少量的变量和n较小的特例，当变量增多，或是n变大，这是阶乘级的时间复杂度哦！
4 w6 e, k9 Z+ s$ r
作者:
guoshaoming
时间:
2010-10-25 22:52
回复
maybe_madio
的帖子
' q2 o4 ^6 }0 {1 j+ A1 l
本身这个算法就很具有一般性，如果你增加变量，只要对程序稍加改动就可以了，
5 U* H/ w7 w0 {
for(xm=1;xm<n;xm++)
# p1 m3 S9 k* Y4 i. P: Z; M' T
然后判断语句和输出也做相应改变
8 {8 s3 `) T) D" S$ [9 ^6 k
2 d# V; F) }/ o: m9 ^$ u1 q0 j
作者:
guoshaoming
时间:
2010-10-25 23:17
回复
maybe_madio
的帖子
! p: M5 x. V" A, ?. `! J7 ]
当你的变量大到一定程度的时候，你可以将约束条件写成一个循环语句，判断、输出也可以写成相应的循环语句！
, ]" i5 h# }2 [# ?& P4 H( L
反正程序的总体思路就是上面那个，过多的我就不多说了
% q6 q" q1 o/ P$ r' S- ~, R
作者:
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
