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
Eidgenössische Technische Hochschule Zürich C++
高中数学题，隔板法
相关推荐
点赞 评论 收藏
分享
程序员牛肉：不用，你低估你学历的含金量了。
不用学微服务，重心放到juc，redis和mysql的八股上。然后准备两个简历项目。直接准备明年暑期就好。南京大学都算是国内比较顶尖的985了。明年暑期零实习也能被约面。不用太焦虑 点赞 评论 收藏
分享
阿里云成长空间 747人发布