题目链接

解题思路

首先把满足题目要求的发票保存在向量中，然后用深搜求最优解，其实也可以用01背包！

#include<bits/stdc++.h>
using namespace std;
double ans, total;
vector<double> v;
void dfs(int i, int t, int sumV){
	if(i==t) return;
	dfs(i+1, t, sumV);
	if(sumV + v[i] <= total){
		if(sumV + v[i] > ans) ans=sumV + v[i];
		dfs(i+1, t, sumV+v[i]);
	}
	 
}
int main(){
	int n,k; 
	char c;
	double sum,x; 
	while(cin>>total>>n){
		ans=0;
		if(n==0) break;
		int cnt=0;
		v.clear();
		for(int i=0;i<n;i++){
			cin>>k;
			sum = 0;
			int flag=0;
			for(int j=0; j<k; j++){
				getchar();
				scanf("%c:%lf",&c,&x);
				if(c!='A'&&c!='B'&&c!='C'){
					flag=1;
				}
				if(x>600) flag=1;
				sum+=x;
			}
			if(flag==0 && sum <= 1000.0){
				v.push_back(sum);
			}	
		}
		dfs(0, v.size(), 0);
		printf("%.2f\n",ans);
	}
	
	return 0;
}