5.最大报销额

• 写在前面
• 【问题描述】
• 【输入形式】
• 【输出形式】
• 【样例输入】
• 【样例输出】
• 题解
• • 思路
  • 代码

写在前面

这题我…乱七八糟。10个样例过了4个，但是支棱了很久了。支棱不起来，不支棱了…分享一下失败的题解

【问题描述】

现有一笔经费可以报销一定额度的发票。允许报销的发票类型包括买图书（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

题解

思路

• 1.首先要把可以报销的支票找出来
• 2.然后用动态规划找到最大销售额的支票组合
• 注意：显然，博主的动态规划比较失败，只过了4个样例… 可恶啊！应该是状态转移方程有问题
• 动态规划对我来说还是太难了T.T

代码

#include<iostream>
#include<string> 
#include<vector>
#include<iomanip>
using namespace std;
int main(){
	double q;
	int n;
	while(cin>>q>>n&&n){
		vector<double> check;//存储满足要求的支票
		vector<double> dp;//动态规划数组 
		while(n--){
			double a=0,b=0,c=0,sum=0,temp;
			int m,flag=0;
			cin>>m;
			char type;
			for(int i=0;i<m;i++){
				cin>>type;//输入类型 
				cin.ignore();//忽略 ：
				cin>>temp;//输入
				if(type=='A') a+=temp;
				else if(type=='B') b+=temp;
				else if(type=='C') c+=temp;
				else {
					flag=1;break;//其他类型不允许报销！！！ 
				}
			}
			sum=a+b+c;
			if(a<=600&&b<=600&&c<=600&sum<=1000&&!flag){//这张支票可以报销 
				check.push_back(sum);
				dp.push_back(sum); 
			} 		
		}
		for(int i=1;i<dp.size();i++){
			for(int j=i-1;j>=0;j--){
				if(dp[j]+check[i]<=q)
					dp[i]=max(dp[i],dp[j]+check[i]);//状态转移方程 我们一张一张的加 
			}
		}
		double ans=0;
		for(int i=0;i<dp.size();i++){
			if(dp[i]>ans){
				ans=dp[i];
			}
		} 
		cout<<fixed<<setprecision(2)<<ans<<endl;	 
	}
	return 0;
}