注意超时问题,一个题可能有很多种方法解决,但是想到解决方法的同时一定要考虑这个方法的复杂度,特别是对于acm的题,有可能出现超时的情况,很浪费时间
正式比赛中就很遗憾,血的教训。
下面贴上超时的代码并做出分析,下次绝不能这样了!!!!!!!!!!!!!!!!!!!!!!!!!!!!
Description
现有一笔经费可以报销一定额度的发票。允许报销的发票类型包括买图书(A类)、文具(B类)、差旅(C类),要求每张发票的总额不得超过1000元,每张发票上,单项物品的价值不得超过600元。现请你编写程序,在给出的一堆发票中找出可以报销的、不超过给定额度的最大报销额。
Input
测试输入包含若干测试用例。每个测试用例的第1行包含两个正数 Q 和 N,其中 Q 是给定的报销额度,N(<=30)是发票张数。随后是 N 行输入,每行的格式为:
m Type_1:price_1 Type_2:price_2 ... Type_m:price_m
其中正整数 m 是这张发票上所开物品的件数,Type_i 和 price_i 是第 i 项物品的种类和价值。物品种类用一个大写英文字母表示。当N为0时,全部输入结束,相应的结果不要输出。
m Type_1:price_1 Type_2:price_2 ... Type_m:price_m
其中正整数 m 是这张发票上所开物品的件数,Type_i 和 price_i 是第 i 项物品的种类和价值。物品种类用一个大写英文字母表示。当N为0时,全部输入结束,相应的结果不要输出。
Output
对每个测试用例输出1行,即可以报销的最大数额,精确到小数点后2位。
Sample Input
200.00 3
2 A:23.50 B:100.00
1 C:650.00
3 A:59.99 A:120.00 X:10.00
1200.00 2
2 B:600.00 A:400.00
1 C:200.50
1200.50 3
2 B:600.00 A:400.00
1 C:200.50
1 A:100.00
100.00 0
Sample Output
123.50
1000.00
1200.50
问题:多组案例,输入每组案例中最大报销金额和账单数,账单总金额小于最大报销数并且仅仅包含A,B,C物品的账单才报销,
总金额大于最大报销数的时候可以选取一部分进行报销
第一行输入每组案例的最大报销金额Q和账单数N
下面N行,每行第一个数据输入这个账单上的物品数m,然后是m个物品的名字以及金额
输出每个案例的最大实际报销金额,
分析:本来用的dfs,写程序和调代码用了一个多小时,最后发现没过
分析了一下原因,最坏的情况,最大可报销金额为无穷,每张账单都满足报销条件,那么就要遍历所有选择的可能性
有C(30, 1) + C(30, 2) + C(30, 3) + …… + C(30, n)种可能性
很可能超时嘛
贴超时代码:
#include <stdio.h> #include <string.h> #include <stdlib.h> using namespace std; double ans[35], sum, Q, maxi; int cnt; bool vis[35]; void dfs(double sum) //传递参数的时候吧sum写成double类型了 { if(sum > Q) return; //printf("sum = %.2lf ", sum); for(int i = 0; i < cnt; i++) { if(!vis[i] && sum+ans[i] <= Q) //这里没加等于号,忽略等于的时候也可行 { vis[i] = 1; sum += ans[i]; if(sum > maxi) maxi = sum; dfs(sum); sum -= ans[i]; vis[i] = 0; } } } int main() { double A, B, C, y; int N, m; char x; //freopen("input.txt", "r", stdin); while(scanf("%lf%d", &Q, &N) && N) { sum = 0; cnt = 0; maxi = 0; memset(vis, 0, sizeof(vis)); for(int i = 0; i < N; i++) { int flag = 0; scanf("%d", &m); A = B = C = 0; while(m--) { getchar(); scanf("%c:%lf", &x, &y); switch (x) { case 'A': A += y; break; case 'B': B += y; break; case 'C': C += y; break; default: flag = 1; break; } } if (flag==0 && A<=600 && B<=600 && C<=600 && A + B + C <= 1000 && A+B+C <= Q) { ans[cnt++] = A + B + C; //printf("ans[%d] = %lf ", cnt-1, ans[cnt-1]); } } dfs(0); printf("%.2lf ", maxi); } return 0; }