题目1025：最大报销额 （dfs深度优先搜索）
http://ac.jobdu.com/problem.php?pid=1025
#include <stdio.h>double data[30];int len;double ans,q; void dfs(int k,double sum){ if(k==len) { if(sum>ans) ans=sum; return; } dfs(k+1,sum); if(sum+data[k]<=q) dfs(k+1,sum+data[k]);} int main(){ int n,m; char cc; while(scanf("%lf %d",&q,&n)&&n!=0) { len=0;ans=-1; for(int i=0;i<n;i++) { scanf("%d",&m); double a=0,b=0,c=0,temp,sum=0; int flag=1; while(m--) { scanf(" %c:%lf",&cc,&temp); if(cc=='A') a+=temp; else if(cc=='B') b+=temp; else if(cc=='C') c+=temp; else flag=0; sum+=temp; } if(flag&&sum<=1000&&a<=600&&b<=600&&c<=600) data[len++]=sum; } dfs(0,0); printf("%.2f\n",ans); }} /************************************************************** Problem: 1025 User: 从此醉 Language: C Result: Accepted Time:10 ms Memory:908 kb****************************************************************/