题目描述:
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时,全部输入结束,相应的结果不要输出。
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;
- }