hdu1864最大报销额

概述题目描述： Problem Description 现有一笔经费可以报销一定额度的发票。允许报销的发票类型包括买图书（A类）、文具（B类）、差旅（C类），要求每张发票的总额不得超过1000元，每张发票上，单项物品的价值不得超过600元。现请你编写程序，在给出的一堆发票中找出可以报销的、不超过给定额度的最大报销额。   Input 测试输入包含若干测试用例。每个测试用例的第1行包含两个正数 Q 和

题目描述：

Problem 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时，全部输入结束，相应的结果不要输出。
Output 对每个测试用例输出1行，即可以报销的最大数额，精确到小数点后2位。 思路：原本以为是01背包问题，但是报销额是小数，网上搜下乘以100，想想也对，保留两位小数吗，搜索也能做，但是 不会，但是贪心也可以解决；提交ac了，后来想想有些错误；

代码：

#include<stdio.h>#include<string.h>#include<algorithm>int main(){    double q,sum[33]={0};    int n,i,j;    while(scanf("%lf%d",&q,&n)!=EOF&&n!=0)    {         int len=0;         for(i=0;i<n;i++)         {              int m,flag=0;              double sum1=0;              scanf("%d",&m);              double va=0,vb=0,vc=0;              for(j=0;j<m;j++)              {                   char type;                   double val;                   scanf(" %c:%lf",&type,&val);                   if(type=='A')va+=val;                   else if(type=='B') vb+=val; 每张发票中A类的和不大于600.BC同理。                   else if(type=='C') vc+=val;                   else flag=1;              }              if(va>600||vb>600||vc>600)                 flag=1;              sum1=va+vb+vc;              if(sum1>1000)                flag=1;              if(!flag)                sum[len++]=sum1;        }         std::sort(sum,sum+len);         double sum2=0;         for(i=len-1;i>=0;i--)             if(sum2+sum[i]<=q)               sum2+=sum[i];            printf("%.2lf\n",sum2);    }    return 0;}

背包代码：

#include<stdio.h>#include<string.h>#include<algorithm> int sum[33],dp[3000002];int main(){    double q;    int n,&n)!=EOF&&n!=0)    {         int len=0,tt;         tt=int(q*100);         for(i=0;i<n;i++)         {              int m,&val);                   if(type=='A')va+=val;                   else if(type=='B') vb+=val;                   else if(type=='C') vc+=val;                   else flag=1;              }              if(va>600||vb>600||vc>600)                 flag=1;              sum1=va+vb+vc;              if(sum1>1000)                flag=1;              if(!flag)                sum[len++]=int(sum1*100);        }         memset(dp,sizeof(dp));         for(i=0;i<len;i++)          for(j=tt;j>=sum[i];j--)            if(dp[j]<dp[j-sum[i]]+sum[i])              dp[j]=dp[j-sum[i]]+sum[i];        printf("%.2lf\n",1.0*dp[tt]/100);    }    return 0;}

总结

以上是内存溢出为你收集整理的hdu1864最大报销额全部内容，希望文章能够帮你解决hdu1864最大报销额所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。