4399笔试题
刚刚刷题时遇到这个编程题，求大神解答！（最好是c++，或者Java）
将20个球放进12个不同的袋子，每个袋子可以放0-20个球，有多少种放法？分析如何计算，然后编程解答。
进阶问题：每个袋子只能放0个、2个或3个球，该如何计算？
2017-11-13 10:23 已编辑 广东工业大学 测试工程师
关注
全部评论
CedricCode
中国海洋大学 Java
献丑了。。不知道对不对，dp问题，dp[i][j]表示0-i个袋子装j个球的放法数
public class BallInPackage {
public int ballInPackage(int numsOfBags, int numsOfBalls)
{
int[][] dp = new int[numsOfBags][numsOfBalls + 1];
//initialization
for(int i = 0; i < numsOfBags; i++)
dp[i][0] = 1;
for(int i = 1; i <= numsOfBalls; i++)
dp[0][i] = 1;
//calculate the dp matrix
for(int i = 1; i < numsOfBags; i++) {
for(int j = 1; j <= numsOfBalls; j++) {
int nums = 0;
for(int k = 0; k <= j; k++)
nums += dp[i-1][k];
dp[i][j] = nums;
}
}
return dp[numsOfBags-1][numsOfBalls];
}
public int ballInPackage_Advanced(int numsOfBags, int numsOfBalls)
{
int[][] dp = new int[numsOfBags][numsOfBalls + 1];
//initialization
for(int i = 0; i < numsOfBags; i++)
dp[i][0] = 1;
dp[0][2] = 1; dp[0][3] = 1;
//calculate the dp matrix
for(int i = 1; i < numsOfBags; i++) {
for(int j = 1; j <= numsOfBalls; j++) {
if(j < 2)
dp[i][j] += dp[i-1][j];
else if(j == 2)
dp[i][j] += dp[i-1][j] + dp[i-1][j-2];
else if(j >= 3)
dp[i][j] += dp[i-1][j] + dp[i-1][j-2] + dp[i-1][j-3];
else
dp[i][j] = 0;
}
}
return dp[numsOfBags-1][numsOfBalls];
}
public static void main(String[] args) {
BallInPackage b = new BallInPackage();
System.out.println(b.ballInPackage(12, 20));
System.out.println(b.ballInPackage_Advanced(12, 20));
}
}
Tiket
中南大学 C++
高中数学题，隔板法
相关推荐
查看9道真题和解析
