九度OJ-1025：最大报销额

ゞ浴缸里的玫瑰 2022-08-17 15:14 133阅读 0赞

题目1025：最大报销额

**时间限制：**1 秒

**内存限制：**32 兆

**特殊判题：**否

**提交：**4410

**解决：**1063

**题目描述：**

现有一笔经费可以报销一定额度的发票。允许报销的发票类型包括买图书（A类）、文具（B类）、差旅（C类），要求每张发票的总额不得超过1000元，每张发票上，单项物品的价值不得超过600元。现请你编写程序，在给出的一堆发票中找出可以报销的、不超过给定额度的最大报销额。

**输入：**

测试输入包含若干测试用例。每个测试用例的第1行包含两个正数 Q 和 N，其中 Q 是给定的报销额度，N（N<=30）是发票张数。随后是 N 行输入，每行的格式为：  
m Type\_1:price\_1 Type\_2:price\_2 ... Type\_m:price\_m  
其中正整数 m 是这张发票上所开物品的件数，Type\_i 和 price\_i 是第 i 项物品的种类和价值。物品种类用一个大写英文字母表示。当N为0时，全部输入结束，相应的结果不要输出。

**输出：**

对每个测试用例输出1行，即可以报销的最大数额，精确到小数点后2位。

**样例输入：**

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

**样例输出：**

123.50
    1000.00
    1200.50

**来源：**

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

#include<stdio.h>
    #include<string.h>
    #include<algorithm>
    using namespace std;
    double map[10000];
    int top;
    double erfen(int k,double l,double q)
    {
    	int mark=0;
    	double t=0;
    	for(int i=k;i<top;i++)
    	{
    		if(map[i]<=l)
    		{
    			t=max(erfen(i+1,l-map[i],q),t);
    			mark=1;
    		}
    	}
    	if(mark==0)
    	return q-l;
    	else
    	return t;
    }
    int main()
    {
    	double q;
    	int n;
    	while(scanf("%lf%d",&q,&n)&&n)
    	{
    		int i,j;
    		int b1,b2;
    		b1=0;
    		double ans=0; 
    		for(i=0;i<n;i++)
    		{
    			int yy;
    			scanf("%d",&yy);
    			getchar();
    			b2=0;
    			double w6=0;
    			for(j=0;j<yy;j++)
    			{
    				char a1;
    				scanf("%c:",&a1);
    				double xx;
    				scanf("%lf",&xx);
    				if(a1!='A'&&a1!='B'&&a1!='C')
    				{
    					b2=1;
    				}
    				if(xx>600)
    				{
    					b2=1;
    				}
    				w6+=xx;
    				getchar();
    			}
    			if(b2==0)
    			{
    				map[b1++]=w6;
    			}
    		}
    		top=b1;
    		printf("%.2lf\n",erfen(0,q,q));
    	}
    	return 0;
    }

[2007]: http://ac.jobdu.com/problemset.php?search=2007%E5%B9%B4%E6%B5%99%E6%B1%9F%E5%A4%A7%E5%AD%A6%E8%AE%A1%E7%AE%97%E6%9C%BA%E5%8F%8A%E8%BD%AF%E4%BB%B6%E5%B7%A5%E7%A8%8B%E7%A0%94%E7%A9%B6%E7%94%9F%E6%9C%BA%E8%AF%95%E7%9C%9F%E9%A2%98