分配难题

maybe_madio

      设有4个盒子，标号为1，2，3，4.   有15个颜色相同的小球, 现在要将15个颜色相同的小球分配到4个盒子中,
要求每个盒子至少有一个小球，并且对于盒子中小球的数目，盒子1>盒子2>盒子3>盒子4.  请问一共有多少种分配方法.

漂流者

可以先把15个球排成一排，然后从他们之间的14个间隔里插入3块板，就可以把15个小球分成4份了，用这个思想，可以很容易解决你的问题，隔板法是很经典的东西。

whui

13种。。。。。。。。。。。。。

whui

13种呀。。。。。。。。。。。。。。。。

linmatsas

要是好多好多球好多好多盒子可怎么办呢…………这真是一个问题呀………………不过一时想不出来其他算法了……应该穷举能做呀…………应该用不了几个小时吧…………

guoshaoming

回复 maybe_madio 的帖子
当你的变量大到一定程度的时候，你可以将约束条件写成一个循环语句，判断、输出也可以写成相应的循环语句！
/ j, D' a$ l% H  ]/ g反正程序的总体思路就是上面那个，过多的我就不多说了
% b: D1 K" }5 `6 w' I   

guoshaoming

回复 maybe_madio 的帖子
9 n6 ^7 r/ Q6 L9 w本身这个算法就很具有一般性，如果你增加变量，只要对程序稍加改动就可以了，
5 B$ _+ D$ c1 c3 sfor(xm=1;xm<n;xm++)
$ f& f4 x3 e- o. c7 V, b0 a然后判断语句和输出也做相应改变
3 G4 D0 k) K- g! O% c! w
   

maybe_madio

回复 guoshaoming 的帖子


    虽然对于15来说，比较容易算出， 那如果我的变量再增多呢？ 假设有x1+x2+..xm=n呢？（m<n）
8 s* [3 X* c. E能否有更好的程序算法来解决这个问题呢？ 你的穷举算法也只能适用于少量的变量和n较小的特例，当变量增多，或是n变大，这是阶乘级的时间复杂度哦！
/ J# P- _7 d: R( ?2 k! q- K

guoshaoming

1 b" d; \) m$ x
! v) V/ S4 @! q  f! w0 a+ x回复 maybe_madio 的帖子
# z. c5 A1 O# K  \分配方案如下：
6       4       3       2
* S7 J$ C  V9 N/ c6       5       3       1
4 t. ^* S$ Q0 l7       4       3       1
7       5       2       1
& R+ ^5 u# P4 e" x8       4       2       1
: K. M+ h3 \( ~3 \4 P# u  k: q0 b9       3       2       1
2 ~, M! p% v4 i* b其代码如下：
#include < iostream >

1 |# w5 }1 b! x5 G) y7 d5 Wusing namespace std;
: E- D7 N: J5 y7 |3 G7 m& @3 @" L2 j
& J) x; V! B5 N& [( [
. F( v/ w4 W/ P& r6 m! \% p) Mint main()
{
. T! |/ B3 }  ^) u4 ^! Bint x1,x2,x3,x4;
5 i" J) `; G# cint t=0;

$ R5 h: t9 `# I2 ~0 D6 \0 X( B  Tfor(x1=1;x1<15;x1++)
for(x2=1;x2<15;x2++)
! J; A* D$ [7 b+ jfor(x3=1;x3<15;x3++)
for(x4=1;x4<15;x4++)
{
7 T3 m( i; {* @+ o9 j# ^if((x1+x2+x3+x4==15)&&(x1>x2)&&(x2>x3)&&(x3>x4))
3 R: i$ R9 D3 p& E! B9 g1 ecout<<x1<<"\t"<<x2<<"\t"<<x3<<"\t"<<x4<<endl;
% J3 W- ?, c- i1 v
( @- V  `/ \( z: {0 R5 Q& `}
; K: F" \2 d1 o$ a9 `; b2 B% Oreturn 0;
" O& C7 J3 q2 b& S  r" U}

   

1124629740