2007年第6题
题目地址:http://jobdu.sinaapp.com/problem.php?pid=1025
C语言源码:
//暴力搜索#include<stdio.h>int visited[31];int n;double max,q;double a[31];void dfs(double sum){int i;for(i=0;i<n;i++){if(visited[i]==0){visited[i]=1;if(sum+a[i]<=q)dfs(sum+a[i]);elsedfs(sum);visited[i]=0;}}if(sum>max)max=sum;}int main(){int i,j,top,m,flag;double sum,p;char s;scanf("%lf %d",&q,&n);while(n){top=0;for(i=0;i<n;i++){scanf("%d",&m);sum=0;flag=0;while(m--){scanf(" %c:%lf",&s,&p);if(s!='A'&&s!='B'&&s!='C'||p>600){sum=0;flag=1;continue;}elsesum+=p;}if(flag==0&&sum<=1000)a[top++]=sum;}n=top;max=0;for(i=0;i<31;i++)visited[i]=0;dfs(0);printf("%.2lf\n",max);scanf("%lf %d",&q,&n);}}