解题思路:
这道题提交了好多次都失败了,刚开始想当然地用贪心算法,后来发现错了又用回溯法,但是运行超时,最后采用动态规划顺利解决。这题的解题思路及方法其他题解已经讲得很清楚了。所以此文章仅仅是为了记下自己的代码便于日后自己复习。
注意事项:
参考代码
#include<stdio.h> #if 0 void sort(int a[],int b[],int M); //贪心算法 int main() { int T,M; scanf("%d%d",&T,&M); int a[M],b[M]; for(int i=0;i<M;i++) scanf("%d%d",&a[i],&b[i]); sort(a,b,M); int worth=0; for(int i=0;T>0&&i<M;i++) { if(a[i]<=T) {worth=worth+b[i]; T=T-a[i]; } } printf("%d",worth); return 0; } void sort(int a[],int b[],int M)//按单位时间内价值大小按从大到小冒泡排序 { if(M<=1) return ; for(int k=1;k<M;k++) for(int i=0;i<M-k;i++) if(((float)b[i])/a[i]<((float)b[i+1])/a[i+1]) { int n; n=a[i]; a[i]=a[i+1]; a[i+1]=n; n=b[i]; b[i]=b[i+1]; b[i+1]=n; } } /************************************************************/ int max(int a,int b) //回溯法 { return a>b?a:b; } int solve(int a[],int b[],int T,int M) { if(M==0) return 0; if(a[M-1]<=T) return max(solve(a,b,T-a[M-1],M-1)+b[M-1],solve(a,b,T,M-1)); else return solve(a,b,T,M-1); } int main() { int T,M; scanf("%d%d",&T,&M); int a[M],b[M]; for(int i=0;i<M;i++) scanf("%d%d",&a[i],&b[i]); printf("%d",solve(a,b,T,M)); } #endif /************************************************************/ int max(int a,int b) //动态规划 { return a>b?a:b; } void solve(int matrix[101][1001],int a[],int b[],int M,int T) { for(int m=1;m<=M;m++) for(int t=1;t<=T;t++) { if(a[m]<=t) matrix[m][t]=max(matrix[m-1][t-a[m]]+b[m],matrix[m-1][t]); else matrix[m][t]=matrix[m-1][t]; } } int main() { int T,M; scanf("%d%d",&T,&M); int a[M+1],b[M+1]; for(int i=1;i<=M;i++) scanf("%d%d",&a[i],&b[i]); int matrix[101][1001]; solve(matrix,a,b,M,T); printf("%d",matrix[M][T]); }
:
0.0分
0 人评分