解题思路:
注意事项:
参考代码:#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
int dp[105][1005];
int main(int argc, char const *argv[]) {
int t,x;
cin>>t>>x;//t为总时间,x是个数
int time[105],value[105];
for(int i=1;i<=x;i++){
cin>>time[i]>>value[i];//输入数据
}
memset(dp,0,sizeof(dp));//对数组进行初始化
for(int i=1;i<=x;i++){
for(int j=t;j>=1;j--){//时间从最大开始
if(j>=time[i]){
dp[i][j]=max(dp[i-1][j],dp[i-1][j-time[i]]+value[i]);
//进行最大价值的更新
//如果不放入则t时间不变,如果放入则减去时间。这就相当于往背包里面放入东西
//总时间就相当于背包的容量。
//减去时间之后还要加上第i个价值,然后进行更新
}
else
dp[i][j]=dp[i-1][j];
//第i个东西的价值已将放不进背包了,所以输出i-1.
}
}
cout<<dp[x][t]<<endl;
return 0;
}
0.0分
1 人评分
C语言训练-素数问题 (C语言代码)浏览:995 |
C语言程序设计教程(第三版)课后习题9.3 (Java代码)浏览:957 |
C语言程序设计教程(第三版)课后习题9.8 (Java代码)浏览:1638 |
A+B for Input-Output Practice (IV) (C语言代码)浏览:451 |
printf基础练习2 (C语言代码)浏览:741 |
C语言程序设计教程(第三版)课后习题8.8 (C语言代码)浏览:1420 |
sizeof的大作用 (C语言代码)浏览:1450 |
矩阵乘方 (C语言代码)浏览:1025 |
简单的a+b (C语言代码)浏览:507 |
母牛的故事 (C语言代码)浏览:562 |