2007年浙江大学计算机及软件工程研究生机试真题

http://ac.jobdu.com/problem.php?pid=1025  最大报销额

//将题目中数字都扩大100倍变成整数，就可看作经典的01背包问题 //设报销额度为背包上限，可报销支票金额为价格，可报销支票金额为重量 //a[]存的既是价格，又是重量 #include<iostream> #include<cstdio> using namespace std;int a[32]; //存的既是价格，又是重量 const int MAX = 3000005; int f[MAX]; int V; //背包的体积void ZeroOnePack(int cost, int weight) {int v;for (v = V; v >= cost; v--)f[v] = f[v] > (f[v - cost] + weight) ? f[v] : (f[v - cost] + weight); } int main(void) {int i,j,n,m,k,flag;double q,price,A,B,C;char type;while(scanf("%lf %d",&q,&n)!=EOF){if(!n)break;k=0;for(i=0;i<n;i++){scanf("%d",&m);A=B=C=0;flag=0;for(j=0;j<m;j++){getchar();scanf("%c:%lf",&type,&price);if(type=='A')A+=price;else if(type=='B')B+=price;else if(type=='C')C+=price;elseflag=1;}if(!flag){if(A+B+C<=1000 && A<=600 && B<=600 && C<=600) //合法的发票a[k++]=(int)(100*(A+B+C));}}V=q*100;for(i=0;i<=V;i++) //没有要求把背包装满{f[i]=0;}for(i=0;i<k;i++)ZeroOnePack(a[i],a[i]);printf("%.2lf\n",f[V]/100.0);}return 0; }
与50位技术专家面对面20年技术见证，附赠技术全景图

总结

以上是生活随笔为你收集整理的2007年浙江大学计算机及软件工程研究生机试真题的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。