代码有两个没过,找不出原因请大家帮忙看看
int MaxDayMonth(int year, int month){
if(year<0||month<1||month>12)return 0;
switch (month){
case 1:return 31;break;
case 2:
if(IsLeapYear(year)) {
return 29;
}
else
{
return 28;
}
break;
case 3:return 31 ;break;
case 4:return 30;break;
case 5:return 31;break;
case 6:return 30;break;
case 7:return 31;break;
case 8:return 31;break;
case 9:return 30;break;
case 10:return 31;break;
case 11:return 30;break;
case 12:return 31;break;
}
}
这句: if(year<0||month<1||month>12) return 0; 应该为: if(year < 1 || month < 1 || month > 12) return 0;
看着没啥问题
应该含有闰年判断函数的代码吧,是不是闰年判断有错啊
IsLeapYear这个怎么写的,2100年不是闰年
多说一句,都return了,就不用break了吧
特殊情况可以放到switch的default分支去
1. 创建数据表,竖向为备选项及其成本/收益,横向为手中的成本能力,空白部分为最大收益。
2. 依次填充空白的部分。
因为400kg的黄金的代价为5个人力,所以第一行空白的1-4个工人的位置,最大收益为0.
此时的w为1,2,3,4,但是p[0] = 5, w < p[0], 推进公式为:
F(n,w) = F(n-1,w) (n>1, w<p[n-1])
则,
F(1,1) = F(1-1,1) = F(0,1) = 0
F(1,2) = F(1-1,2) = F(0,2) = 0
F(1,3) = F(1-1,3) = F(0,3) = 0
F(1,4) = F(1-1,4) = F(0,4) = 0
w为5,6,7,8,9,10时, w >= p[0], 推进公式为:
F(n,w) = max(F(n-1,w), F(n-1,w-p[n-1])+g[n-1]) (n>1, w≥p[n-1]);
则,
F(1, 5) = max(F(0, 5), F(0, 0) + 400) = 400
F(1, 6) = max(F(0, 6), F(0, 1) + 400) = 400
F(1, 7) = max(F(0, 7), F(0, 2) + 400) = 400
F(1, 8) = max(F(0, 8), F(0, 3) + 400) = 400
F(1, 9) = max(F(0, 9), F(0, 4) + 400) = 400
F(1, 10) = max(F(0, 10), F(0, 5) + 400) = 400
对于第二行,
因为500kg的黄金的代价为5个人力,所以第二行空白的1-4个工人的位置,最大收益为0.
此时的w为1,2,3,4,但是p[1] = 5, w < p[0], 推进公式为:
F(n,w) = F(n-1,w) (n>1, w<p[n-1])
则,
F(2,1) = F(2-1,1) = F(1,1) = 0
F(2,2) = F(2-1,2) = F(1,2) = 0
F(2,3) = F(2-1,3) = F(1,3) = 0
F(2,4) = F(2-1,4) = F(1,4) = 0
w为5,6,7,8,9,10时, w >= p[1], 推进公式为:
F(n,w) = max(F(n-1,w), F(n-1,w-p[n-1])+g[n-1]) (n>1, w≥p[n-1]);
则,
F(2, 5) = max(F(1, 5), F(1, 0) + 500) = 500
F(2, 6) = max(F(1, 6), F(1, 1) + 500) = 500
F(2, 7) = max(F(1, 7), F(1, 2) + 500) = 500
F(2, 8) = max(F(1, 8), F(1, 3) + 500) = 500
F(2, 9) = max(F(1, 9), F(1, 4) + 500) = 500
F(2, 10) = max(F(1, 10), F(1, 5) + 500) = 900
对于第三行,
因为200kg的黄金的代价为3个人力,所以第三行空白的1-2个工人的位置,最大收益为0.
此时的w为1,2,但是p[1] = 3, w < p[0], 推进公式为:
F(n,w) = F(n-1,w) (n>1, w<p[n-1])
则,
F(3,1) = F(3-1,1) = F(2,1) = 0
F(3,2) = F(3-1,2) = F(2,2) = 0
当w为3,4,5,6,7,8,9,10时,w >= p[2] 推进公式为:
F(n,w) = max(F(n-1,w), F(n-1,w-p[n-1])+g[n-1]) (n>1, w≥p[n-1]);
则,
F(3, 3) = max(F(2, 3), F(2, 0) + 200) = 200
F(3, 4) = max(F(2, 4), F(2, 1) + 200) = 200
F(3, 5) = max(F(2, 5), F(2, 2) + 200) = 500
F(3, 6) = max(F(2, 6), F(2, 3) + 200) = 500
F(3, 7) = max(F(2, 7), F(2, 4) + 200) = 500
F(3, 8) = max(F(2, 8), F(2, 5) + 200) = 700
F(3, 9) = max(F(2, 9), F(2, 6) + 200) = 700
F(3, 10) = max(F(2, 10), F(2, 7) + 200) = 900
以此类推
第五行
所以最佳答案是900.
public int getBestGoldMiningV2(int w, int[] p, int[] g){
//创建表格
int[][] resultTable = new int[g.length+1][w+1];
//填充表格
for(int i = 1; i <= g.length; i++){
for(int j = 1; j <= w; j++){
if(j<p[i-1]){
// 当前剩余成本不足以选择当前的方案
resultTable[i][j] = resultTable[i-1][j];
}else{
// 当前成本足够,两个方案的收益取最大值
resultTable[i][j] = Math.max(resultTable[i-1][j], resultTable[i-1][j-p[i-1]]+ g[i-1]);
}
}
}
//返回最后1个格子的值
return resultTable[g.length][w];
}
其实我们并不关心j < p[i-1]的部分
public int getBestGoldMiningV3(int w, int[] p, int[] g){
int[] results = new int[w+1];
//填充一维数组
for(int i = 1; i <= g.length; i++){
for(int j = w; j >= 1; j--){
if(j >= p[i-1]){
results[j] = Math.max(results[j], results[j - p[i-1]]+ g[i-1]);
}
}
}
//返回最后1个格子的值
return results[w];
}