最大报销额

#include <stdio.h>
#include <string.h>

struct Info1
{
    double hash[300];
    double tot;
    int flag;
};

struct Info1 fapiao[35];

double maxi=-1;
double Q;

void DFS(int i,double sum,int n)
{
    if(i==n)
    {
        if(sum>maxi)
        {
            maxi=sum;
        }
        return;
    }
    DFS(i+1,sum,n);
    if(sum+fapiao[i].tot<=Q&&fapiao[i].flag==1)
    {
        DFS(i+1,sum+fapiao[i].tot,n);
    }

}

int main()
{
    int N;
    int i,j;
    char str[50];
    char ch;
    while(scanf("%lf %d",&Q,&N)!=EOF&&N)
    {
        int m;
        for(i=0;i<N;i++)
        {
            fapiao[i].flag=1;
            fapiao[i].tot=0;
            memset(fapiao[i].hash,0,sizeof(fapiao[i].hash));
            scanf("%d",&m);
            for(j=0;j<m;j++)
            {
                scanf("%s",str);
                double temp;
                sscanf(str,"%c:%lf",&ch,&temp);
                fapiao[i].hash[ch]+=temp;
                fapiao[i].tot+=temp;
                if(fapiao[i].hash[ch]>600) fapiao[i].flag=0;
                if(ch!='A'&&ch!='B'&&ch!='C')
                {
                    fapiao[i].flag=0;
                }
            }
            if((int)fapiao[i].tot>1000) fapiao[i].flag=0;
        }
        DFS(0,0,N);
        printf("%.2f\n",maxi);
    }
    return 0;
}

	

package com.speical.first;

import java.util.Scanner;

/** 
* 带有约束的0 1背包问题
* 
* 思路： dp[j] = Math.max(dp[j], dp[j - prices[i]] + prices[i]);
* 
* 注意此题的背包大小为double型，所以我们可以乘以10的次方来消除小数点
* 转换为我们熟知的int型的背包
* 
* 同时对于不合法的发票（对应不合法的物体）我们把此物体的体积设置为背包的最大体积加1
* 这样当考虑该物体时，肯定不会考虑这个物体（发票）
* @author special
* @date 2018年1月7日 下午2:17:26
*/
public class Pro132 {

    public static int getMaxPrice(int[] prices, int n, int maxPrice){
        int[] dp = new int[maxPrice + 1];
        for(int i = 1; i <= n; i++){
            for(int j = maxPrice; j >= prices[i]; j--){
                dp[j] = Math.max(dp[j], dp[j - prices[i]] + prices[i]);
            }
        }
        return dp[maxPrice];
    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner input = new Scanner(System.in);
        while(input.hasNext()){
            double q = input.nextDouble();
            int n = input.nextInt(), count;
            if(n == 0) break;
            int maxPrice = (int)(q * 100);
            int[] prices = new int[n + 1];
            double A, B, C, price;
            boolean isValid = true;
            for(int i = 1; i <= n; i++){
                count = input.nextInt();
                A = B = C = 0;
                isValid = true;
                while(count-- > 0){
                    String data = input.next();
                    String[] dataArray = data.split(":");
                    price = Double.parseDouble(dataArray[1]);
                    if(dataArray[0].equals("A")){
                        A += price;
                    }else if(dataArray[0].equals("B")){
                        B += price;
                    }else if(dataArray[0].equals("C")){
                        C += price;
                    }else{    // 非 A B C 就是不合法
                        isValid = false;
                    }
                 }
                double total = A + B + C; 
                if(!isValid || A > 600 || B > 600 || C > 600 || total > 1000){
                    prices[i] = maxPrice + 1;
                }else{
                    prices[i] = (int)(total * 100);
                }
            }
            System.out.format("%.2f\n", getMaxPrice(prices, n, maxPrice) / 100.0);
        }
    }

}

def cost_by_idx(invoice_list, max_cost, base_idx):
    res = 0.0
    for i in range(base_idx, len(invoice_list)):
        if res + invoice_list[i] <= max_cost:
            res += invoice_list[i]

    return res


while True:
    try:
        in_list = input().split()
        max_cost = float(in_list[0])
        invoice_num = int(in_list[-1])

        # 发票数 == 0，结束程序
        if invoice_num == 0:
            break

        invoice_list = [] # 保存各发票可以报销的额度

        for i in range(invoice_num):
            invoice_data = input().split()[1:]
            allowed_costs = []

            for item in invoice_data:
                cate, cost = item.split(':')

                # 如果此发票包含不可报销类型，则跳过此发票
                if cate not in ['A', 'B', 'C']&nbs***bsp;float(cost) > 600:
                    break
                allowed_costs.append(float(cost))
            else:
                # 添加单张发票可以报销的总额
                if sum(allowed_costs) <= 1000:
                    invoice_list.append(sum(allowed_costs))

        invoice_list.sort(reverse=True)

        res = 0.0

        for i in range(len(invoice_list)):
            res = max(res, cost_by_idx(invoice_list, max_cost, i))

        print('{:.2f}'.format(res))
    except Exception:
        break

#include<iostream>
#include<iomanip>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;

struct fapiao
{
    bool tag=true;//默认可以用
    double A=0,B=0,C=0;
    int num;
    double sum;
};

double string2double(string &S)
{
    int len=S.size()-3;
    double a=0,b=0;
    for(int i=2;i<len;i++)
        a=a*10+S[i]-'0';
    b=(S[len+1]-'0')*0.1+(S[len+2]-'0')*0.01;
    return a+b;
}

bool cmp(fapiao a,fapiao b)
{
    return a.sum>b.sum;
}

int main()
{
    double Q,N;
    while(cin>>Q>>N)
    {
        if(N==0)
            break;
        vector<fapiao> fas(N);
        for(int i=0;i<N;i++)
        {//i表示发票
            int num;
            string S;
            cin>>num;
            fas[i].num=num;
            for(int j=0;j<num;j++)
            {//j表示发票内的款项
                cin>>S;
                if(S[0]!='A'&&S[0]!='B'&&S[0]!='C')
                {
                    fas[i].tag=false;
                }else if(S[0]=='A')
                {
                    fas[i].A+=string2double(S);
                }else if(S[0]=='B')
                {
                    fas[i].B+=string2double(S);
                }else if(S[0]=='C')
                {
                    fas[i].C+=string2double(S);
                }
            }
            fas[i].sum=fas[i].A+fas[i].B+fas[i].C;
            if(fas[i].sum>1000||fas[i].A>600||fas[i].B>600||fas[i].C>600)
            {
                fas[i].tag=0;
            }
        }//将每一张发票存储好了
        sort(fas.begin(),fas.end(),cmp);
        double max=0;//max是最大的那次贪心
        double sum=0;//每一次贪心得到的由sum来存储
        for(int j=0;j<fas.size();j++)
        {//多次贪心
            sum=0;
            for(int i=j;i<fas.size();i++)
            {
                if(sum+fas[i].sum<=Q&&fas[i].tag==true)
                {
                    sum+=fas[i].sum;
                }
            }
            if(sum>max)
            max=sum;
        }
            cout<<fixed<<setprecision(2)<<max<<endl;
    }
}

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
using namespace std;

int main(){
	int n;
	double q;
	vector<double> v;
	while(scanf("%lf %d", &q, &n) != EOF){
		if(n == 0) break;
		for(int i = 0; i < n; i++){
			int num;
			scanf("%d", &num);
			double sum = 0;
			bool flag = true;
			for(int j = 0; j < num; j++){ 
				char type;
				double price;
				getchar(); 
				scanf("%c:%lf", &type, &price);
				if((type != 'A' && type != 'B' && type != 'C') || price > 600) flag = false;
				sum += price;
			}
			if(flag && sum <= q){
				v.push_back(sum);
			}
		}
		sort(v.begin(), v.end());
		double maxsum = 0;
		for(int i = 0; i < v.size(); i++){
			double sum = v[i];
			for(int j = i + 1; j < v.size(); j++){
				if(sum + v[j] <= q) sum += v[j];
				else break;
			}
			maxsum = max(maxsum, sum);
		}
		printf("%.2f\n", maxsum);
	} 
	return 0;
}

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;

int book[31];
double data[31];
double max_money;

void DFS(double sum,double Q,int t)
{
    if(sum > Q) return;
    if(sum <= Q)
    {
        max_money = max(max_money,sum);
    }
    for(int i = 0;i < t;i++)
    {
        if(!book[i])
        {
            book[i] = 1;
            DFS(sum + data[i],Q,t);
            book[i] = 0;
        }
    }
}

int main()
{
    double Q,price;
    int N,m;
    char type;
    while(cin >> Q >> N && N)
    {
        int t = 0;
        while(N--)
        {
            cin >> m;
            double v_total = 0,v_a = 0,v_b = 0,v_c = 0;
            bool flag = true;
            while(m--)
            {
                scanf(" %c:%lf",&type,&price);
                if(type == 'A')
                {
                    v_a += price;
                }
                else if(type == 'B')
                {
                    v_b += price;
                }
                else if(type == 'C')
                {
                    v_c += price;
                }
                else
                {
                    flag = false;
                }
                v_total += price;
                if(v_a > 600 || v_b > 600 || v_c > 600) flag = false;
                if(v_total > Q || v_total > 1000) flag = false;
            }
            if(m == -1 && flag)
                data[t++] = v_total;
        }
        max_money = 0;
        DFS(0,Q,t);
        printf("%.2lf\n",max_money);
    }
    return 0;
}

#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
int dp[3003000]={0};
void init(){
	for(int i=0;i<=3000000;i++)
		dp[i]=0;
}
int main(){
	double s;
	int n;
	while(cin>>s>>n&&n){
		init(); 
		int m;
		int num=1;
		double g[100]={0};
		for(int i=1;i<=n;i++){
			int book=1;
			double h[3]={0};
			cin>>m;
			string p;
			for(int j=1;j<=m;j++){
				cin>>p;
				char k=p[0];
				if(k!='A'&&k!='B'&&k!='C')
					book=0;
				else{
					double ans=0;
					int mr;
					for(int l=2;l<p.size();l++){
						if(p[l]=='.'){
							mr=l;
							break;
						}
						ans*=10;
						ans+=p[l]-'0';
					}
					ans+=0.1*(p[mr+1]-'0');
					ans+=0.01*(p[mr+2]-'0');
					h[p[0]-'A']+=ans;
				}
			}
			for(int j=0;j<3;j++){
				if(h[j]>600){
					book=0;
					break;
				}
			}
			double judge=0;
			for(int j=0;j<3;j++){
				judge+=h[j];
				if(judge>1000){
					book=0;
					break;
				}
			} 
			if(judge>1000)
				book=0;
			if(book==1){
				for(int j=0;j<3;j++)
					g[num]+=h[j];
				num++;
			}
		}
		int v[50]={0};
		int w[50]={0};
		for(int i=1;i<num;i++){
			int o=g[i]*100;
			v[i]=o;
			w[i]=o;
		}
		int zong=s*100;
		for(int i=1;i<num;i++){
			for(int j=zong;j>=v[i];j--){
				dp[j]=max(dp[j-v[i]]+w[i],dp[j]);
			}
		}
		double gg=double(dp[zong])/double(100);
		printf("%.2lf\n",gg);
	}
	return 0;
} 

#include<bits/stdc++.h>
using namespace std;
//发票上的每一项
typedef struct item{ 
    char type; //类型
    double price; //额度
}item;
int n;
int index_; //index_记录有效发票的数目
double a[30]; //用于存储符合要求的发票的面额
double limit,maxValue; //给定的报销额  所求蕞大报销额 
double sum;
double money;
vector<item>v; //每个用例的每一行输入的发票
//判断该张发票是否符合要求
int judge(int n)
{
   
    for(int i=0;i<n;i++)
    {
        if(v[i].type<'A'||v[i].type>'C')
            return 0;
        if(v[i].price>600)
            return 0;
        sum+=v[i].price;
    }
    if(sum>1000||sum>limit)
        return 0;
    return 1;
}
//背包问题  递归找出蕞大报销额度 
void find(int i)
{
    if(i==index_) //边界条件
    {
        if(money>maxValue)
            maxValue = money;
        return;
    }
    if(money + a[i] <= limit) 
    {
        money = money + a[i];
        find(i + 1);
        money = money - a[i]; //回溯
    }
    find(i + 1);
}
int main()
{
    char s[15];
    int num;
    int i,j;
    while(cin>>limit>>n&&n!=0)
    {
        memset(a,0,sizeof(a));
        v.clear();
        index_ = 0; 
        maxValue = 0;
        money = 0;
        for(i=0;i<n;i++)
        {
            sum = 0;
            cin>>num;
            for(j=0;j<num;j++)
            {
                scanf("%s",s);
                item t;
                //利用sscanf 从字符串读入
                sscanf(s,"%c:%lf",&t.type,&t.price);
                v.push_back(t);
            }
            if(judge(num))
           { 
              a[index_++]=sum;
           }
            v.clear();
        }
        find(0);
        cout<<fixed<<setprecision(2)<<maxValue<<endl;
        
        
    }
    return 0;
}

#include<cstdio>

#include<cstring>

#include<algorithm>
using namespace std;
const int maxn=100030100+5;//30张1000元的发票(扩大100倍)

int max_val; //可报销总额
int dp[maxn];

int cnt; //合法发票数
int val[maxn];//每张合法发票的额度

int main()
{
double v;
int n;
while(scanf("%lf%d",&v,&n)==2 && n)
{
cnt=0;
max_val=(int)(v*100);
for(int i=1;i<=n;i++)
{
int num;
char type;//商品类型
double va=0,vb=0,vc=0;
scanf("%d",&num);
bool flag=true;//合法发票
while(num--)
{
scanf(" %c:%lf",&type,&v);

            if(type=='A') va+=v;
            else if(type=='B') vb+=v;
            else if(type=='C') vc+=v;
            else flag=false;//含有其他种类商品
        }

        if(flag && va<=600 && vb<=600 && vc<=600 && va+vb+vc<=1000)
            val[++cnt]=(int)((va+vb+vc)*100);
    }

    memset(dp,0,sizeof(dp));

    for(int i=1;i<=cnt;i++)
        for(int j=max_val;j>=val[i];j--)
            dp[j] = max(dp[j],dp[j-val[i]]+val[i]);

    printf("%.2lf\n",(dp[max_val])/100.0 );
}
return 0;

}

#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
vector<float> validCheck;
float Q, curMoney, maxMoney;
int N, validCheckNum;
void FindMaxMoney(int index) {
    if (index == validCheckNum) {
        if (curMoney > maxMoney)
            maxMoney = curMoney;
        return;
    }
    if (curMoney + validCheck[index] <= Q) {
        curMoney += validCheck[index];
        FindMaxMoney(index + 1);
        curMoney -= validCheck[index];
    }
    FindMaxMoney(index + 1);
}
int main(void) {
    while (cin >> Q >> N && N != 0) {
        vector<float>().swap(validCheck);
        for (int i = 0; i < N; i++) {
            int itemNum, valid = 1;
            float money, sum = 0;
            char checkType;
            cin >> itemNum;
            for (int j = 0; j < itemNum; j++) {
                scanf(" %c:%f", &checkType, &money);
                if ((checkType == 'A' || checkType == 'B' || checkType == 'C') && money <= 600)
                    sum += money;
                else 
                    valid = 0;
            }
            if (valid == 1 && sum <= 1000)
                validCheck.push_back(sum);
        }
        validCheckNum = validCheck.size();
        maxMoney = 0, curMoney = 0;
        FindMaxMoney(0);
        printf("%.2f\n", maxMoney);
    }
    return 0;
}

}