这个问题,看似是一个简单的排列组合问题,但是加上不同的限制条件,会演变成不同的问题,感觉很奇妙,就总结一下列举下来

问题一

  问题描述:把m个同样的苹果放在n个同样的盘子里,允许有的盘子空着不放,问有多少种不同的分法?(注:5,1,1和1,1,5是同一种分法)

解题分析:

  设f(m,n)为m个苹果,n个盘子的放法数目,则先对n作讨论,

  • 当n>m:则必定有n-m个盘子永远空着,去掉它们对摆放苹果方法数目不产生影响。即 if(n>m) f(m,n) = f(m,m)
  • 当n <= m:不同的放法可以分成两类:含有0的方案数,不含有0的方案数
  1. 含有0的方案数,即有至少一个盘子空着,即相当于 f(m,n)=f(m,n-1);
  2. 不含有0的方案数,即所有的盘子都有苹果,相当于可以从每个盘子中拿掉一个苹果,不影响不同放法的数目,即 f(m,n)=f(m-n,n).而总的放苹果的放法数目等于两者的和,即 f(m,n)=f(m,n-1)+f(m-n,n)

递归出口条件说明:

  • 当n=1时,所有苹果都必须放在一个盘子里,所以返回1;
  • 当m==0(没有苹果可放)时,定义为1种放法;

用递归解法

int fun(int m, int n) {//m个苹果放在n个盘子中共有几种方法
if(m==0 || n==1)
return 1;
if(n>m)
return fun(m,m);
else
return fun(m,n-1)+fun(m-n,n);
}

用动态规划解法:

                        int[][] mat=new int[m+1][n+1];
for(int i = 0; i <=m; i++) {
mat[i][0]=0;
mat[i][1]=1;
}
for(int i = 0; i <=n; i++) {
mat[0][i]=1;
}
for (int i = 1; i <=m; i++) {
for(int j = 1; j <=n; j++) {
if(i<j)
mat[i][j]=mat[i][i];
else
mat[i][j]=mat[i][j-1]+mat[i-j][j]; }
}
return mat[m][n];

问题二

  问题描述:将整数N分成K个整数的和且每个数大于等于A小于等于B,求有多少种分法

int Dynamics(int n, int k, int min){ //将n分为k个整数,最小的大于等于min,最大的不超过B
if(n < min) return 0; //当剩下的比min小,则不符合要求,返回0
if(k == 1) return 1;
int sum = 0;
for(int t = min; t <= B; t++)
{
sum += Dynamics(n-t, k-1, t);
}
return sum;
}

问题三

  m---->相同, n---->相同, 不能为空。将m个苹果放进n个盘子中,有多少种方法。同时注意例如1、2和2、1这两种方案是一种方案。

  思路,先把每个盘子都放一个苹果,这样问题就转化为:m-n个苹果放进n个盘子里,盘子允许空,即问题1

05-11 13:36