当前位置: 首页 > >

【组合数学】 排列组合详解 (dfs和母函数做法)

发布时间:

排列组合:

题目链接:排列组合



有n种物品,并且知道每种物品的数量。要求从中选出m件物品的排列数。例如有两种物品A,B,并且数量都是1,从中选2件物品,则排列有"AB","BA"两种。


Input:


每组输入数据有两行,第一行是二个数n,m(1<=m,n<=10),表示物品数,第二行有n个数,分别表示这n件物品的数量。


Output:


对应每组数据输出排列数。(任何运算不会超出2^31的范围)



分析:


题意已经很明显了,就是求多重集的排列方案数。?


我一开始用dfs回溯搜索写了一发过了,代码如下:


int n,m;
int num[20];
int ans=0;

void dfs(int step){
if(step==m){
ans++;
return ;
}
for(int i=0;i if(num[i]){
num[i]--;
dfs(step+1);
num[i]++;
}
}

int main()
{
while(~scanf("%d%d",&n,&m)){
ans=0;
for(int i=0;i scanf("%d",&num[i]);
dfs(0);
printf("%d
",ans);
}
return 0;
}

?代码很短,方法也很简单,但是这题数据太水了,其实我自己就把自己hack了:



10 10


1 2 3 4 5 6 7 8 9 10



这组数据用上面这段代码不知道要跑多久?


然后我又改用了母函数的做法,0ms就过了%%%


?代码如下:


#include
#include
#include
using namespace std;

int fact[15];

void fact_calculate(){//阶乘计算
fact[0]=fact[1]=1;
for(int i=2;i<=10;i++)
fact[i]=i*fact[i-1];
}

int main()
{
int n,m;
double c[15],temp[15]; //c数组存放系数
int num[15]; //存放第i种物品有几个
fact_calculate();
while(~scanf("%d%d",&n,&m)){
memset(c,0,sizeof(c));
for(int i=1;i<=n;i++)
scanf("%d",&num[i]);

for(int i=0;i<=num[1];i++) //c数组初始化第一个多项式的系数
c[i]=1.0/fact[i];


for(int i=2;i<=n;i++){ //i表示运算到第几个多项式
memset(temp,0,sizeof(temp));
for(int j=0;j<=m;j++) //循环到m项就可以,因为求的是m排列,后面的项计算了也没有意义
for(int k=0;k<=num[i]&&k+j<=m;k++)
temp[k+j]+=(1.0*c[j]/fact[k]);

for(int j=0;j<=m;j++)
c[j]=temp[j];
}

printf("%.0f
",c[m]*fact[m]);
}

return 0;

}

?



友情链接: