将20个球放进12个不同的袋子，每个袋子可以放0-20个球，

[问答题]

将20个球放进12个不同的袋子，每个袋子可以放0-20个球，有多少种放法？分析如何计算，然后编程解答。

进阶问题：每个袋子只能放0个、2个或3个球，该如何计算？

[微笑]

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
//        写入球的个数
         int ball;
//        写入袋子的个数
         int pack;
         Scanner scan = new Scanner(System.in);
         System.out.println("请输入球的个数");
         ball = Integer.parseInt(scan.next());
         System.out.println("袋子个数");
         pack = Integer.parseInt(scan.next());
         System.out.println(getban(ball, pack));

    }


//    隔板法
    public static long getban(int ball,int pack)
    {
//        由于无法保证每个袋子都能装上一个球，无法使用隔板法，
//        所以故意往每个袋子加1个球，当排序的时候可以往每个袋子里减一个球就可以了
        long result = 1;
        int newball = ball + pack;
//        所以每个球的空隙有newball -1个
        int newballair = newball -1;
//        因为需要放入12-1个袋子（插入12-1块板），所以用公式C（newballair,pack-1）
        /*
         * C(m,n) = m!/n!*(m-n)!
         */
        for(int i = newballair - (pack - 1) + 1; i <= newballair ; i++)
        {
            result *= i;
        }
        return result / factorial(pack-1);
    }

//    阶乘方法
    public static long factorial(int num)
    {
        if(num == 1)
        {
            return 1;
        }
        else
        {
            return num * factorial(num-1);
        }
    }
}

发表于 2019-09-11 02:34:06 回复(1)

Laanyuue

public int ballBag(int bag, int ball) {
        int[][] dp = new int[bag + 1][ball + 1];
        int i, j, k, sum;

        for (i = 1; i <= bag; i++) {
            dp[i][0] = 1;
        }//无论几个包，放入0个球的方法只有一种
    
        for (j = 0; j <= ball; j++) {
            dp[1][j] = 1;
        }//无论几个球，放入1个包的方法也只有一种
    
        for (i = 2; i <= bag; i++) {
            for (j = 1; j <= ball; j++) {
                sum = 0;
                for (k = 0; k <= j; k++) {
                    sum += dp[i - 1][k];
                }
                dp[i][j] = sum;
            }
        }
        return dp[bag][ball];
    }

发表于 2020-03-11 18:01:57 回复(0)

蘑菇炭改

数学方法：如果我们把单个小球放入某个袋子设为x1, x2, ... , x12，则x1 + x2 + ... + x12 = 1，其中x1, x2, ... , x12 的值为 0 或 1，那么单个小球放入12个袋子的种类数即为这个方程解的个数。那么20个小球即可看做x1 + x2 + ... + x12 = 20，其解的个数即为我们所求的种类数。根据隔板法可以得出种类数为C(20+12-1, 20)。另一方面，如果我们把20个小球的种类数，看做(x1 + x2 + ... + x12)^20展开式的项数，也可以得到相同的结论。

非数学方法：DP。

进阶问题：DP。进阶问题反而运算量减少了。

发表于 2020-04-28 14:40:58 回复(0)