解题思路:这道题采用01背包算法
注意事项:
参考代码:
public class test61 {
public static void main(String[] args) {
Scanner data=new Scanner(System.in);
int T=data.nextInt();
int M=data.nextInt();
int[][] a=new int[M+1][T+1];//构建一个dp数组,用来存放最优解,创建该数组要比正常的大一,因为下面的循环是从1开始的
int[] t=new int[M+1];//这个数组用来存放采各个药的时间,顺序不能变
int[] v=new int[M+1];//这个数组用来存取各个药的价值,顺序不能变
//这个循环用来输入
for (int i=1;i<M+1;i++){
t[i]=data.nextInt();
v[i]=data.nextInt();
}
//这个循环用来计算最优解和存放最优解
for (int i=1;i<M+1;i++){
for (int j=0;j<T+1;j++){
//这个if用来比较,当前物品所需时间大于还剩余的时间
if (t[i]>j){
a[i][j]=a[i-1][j];
}else{
a[i][j]=max(a[i-1][j],a[i-1][j-t[i]]+v[i]);
}
}
}
//最优解存放在最大的下标
System.out.println(a[M][T]);
}
public static int max(int i, int b) {
return i>b? i:b;
}
}
0.0分
2 人评分
C语言程序设计教程(第三版)课后习题5.7 (C语言代码)浏览:636 |
C语言程序设计教程(第三版)课后习题8.9 (C语言代码)浏览:662 |
【蟠桃记】 (C语言代码)浏览:651 |
C语言程序设计教程(第三版)课后习题6.4 (C语言代码)浏览:744 |
兰顿蚂蚁 (C++代码)浏览:1045 |
【简单计算】 (C语言代码)浏览:622 |
简单的for循环浏览:1410 |
C语言训练-大、小写问题 (C语言代码)浏览:681 |
良心推荐——>题解1049:C语言程序设计教程(第三版)课后习题11.1 (C语言描述——简单明了,时间复杂度低)浏览:1287 |
神奇的fans (C语言代码)浏览:986 |