解题思路:贪心算法不适合这题,使用动态规划(递归的一种类似形式)
方法一: #include<iostream> # include<cstring> # define max(a,b) ( a )>( b )?( a ): (b) using namespace std; int main() { int dp[101][1001] , n , t , a [101],v[101] , i , j; // dp[已经判断是否摘取的草药数量][剩余的时间] cin >> t >> n; for(i=1;i<=n;i++) cin >> a[i] >> v[i] ; memset( dp , 0 , sizeof(dp)) ; for(i=1;i<=n;i++) for(j=0;j<=t;j++) //这个的j 对应着剩余的时间 { if( j >= a [i]) dp[i][j] = max ( dp[i-1][j] , dp[i-1][j-a[i]] + v[i] ) ;//放还是不放的选择,如果时间允许采药 else dp[i][j] = dp[i-1][j] ; //时间不允许采药 } cout<<dp[n][t]<<endl; return 0; } 方法二:使用递归(递归算法容易超时,但时简单易懂) #include<cstdio> #include<iostream> #include<algorithm> using namespace std; int a[1000 ] , b[1000] ; //a 记录 时间 ,b 记录 价值 int fac(int n , int t) { int m = 0 ; if ( n == 0 || t == 0) return 0; // 边界 if (a[n-1] > t ) return fac(n-1 , t ); // 时间不可以允许摘这个草药 if(a[n-1] <= t) m = max(fac(n-1 , t - a[n-1] ) + b[n-1] , fac( n - 1 , t) ); return m; } int main(void) { int t , n , i , sum = 0 ; cin >> t >> n ; for(i=0;i< n ;i++) cin >> a[i] >> b[i] ; sum = fac ( n , t ); cout << sum << endl; return 0; }
注意事项:对于数据量大的,递归超时
参考代码:
0.0分
4 人评分
C语言程序设计教程(第三版)课后习题8.5 (C语言代码)浏览:787 |
计算质因子 (C++代码)100以内质数直接打表就好了浏览:1126 |
第一浏览:845 |
C二级辅导-进制转换 (C语言代码)浏览:604 |
简单的a+b (C++语言代码)浏览:837 |
小明A+B (C语言代码)浏览:1181 |
C语言程序设计教程(第三版)课后习题5.5 (C语言代码)浏览:558 |
WU-输出正反三角形 (C++代码)浏览:979 |
C语言程序设计教程(第三版)课后习题6.6 (C++代码)浏览:611 |
printf基础练习2 (C语言代码)浏览:596 |