hdu1864最大报销额

前端之家收集整理的这篇文章主要介绍了hdu1864最大报销额前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。

题目描述:

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了,后来想想有些错误

代码

  1. #include<stdio.h>
  2. #include<string.h>
  3. #include<algorithm>
  4. int main()
  5. {
  6. double q,sum[33]={0};
  7. int n,i,j;
  8. while(scanf("%lf%d",&q,&n)!=EOF&&n!=0)
  9. {
  10. int len=0;
  11. for(i=0;i<n;i++)
  12. {
  13. int m,flag=0;
  14. double sum1=0;
  15. scanf("%d",&m);
  16. double va=0,vb=0,vc=0;
  17. for(j=0;j<m;j++)
  18. {
  19. char type;
  20. double val;
  21. scanf(" %c:%lf",&type,&val);
  22. if(type=='A')va+=val;
  23. else if(type=='B') vb+=val; 每张发票中A类的和不大于600.BC同理。
  24. else if(type=='C') vc+=val;
  25. else flag=1;
  26. }
  27. if(va>600||vb>600||vc>600)
  28. flag=1;
  29. sum1=va+vb+vc;
  30. if(sum1>1000)
  31. flag=1;
  32. if(!flag)
  33. sum[len++]=sum1;
  34. }
  35. std::sort(sum,sum+len);
  36. double sum2=0;
  37. for(i=len-1;i>=0;i--)
  38. if(sum2+sum[i]<=q)
  39. sum2+=sum[i];
  40. printf("%.2lf\n",sum2);
  41. }
  42. return 0;
  43. }

背包代码

  1. #include<stdio.h>
  2. #include<string.h>
  3. #include<algorithm>
  4. int sum[33],dp[3000002];
  5. int main()
  6. {
  7. double q;
  8.  
  9. int n,&n)!=EOF&&n!=0)
  10. {
  11. int len=0,tt;
  12. tt=int(q*100);
  13. for(i=0;i<n;i++)
  14. {
  15. int m,&val);
  16. if(type=='A')va+=val;
  17. else if(type=='B') vb+=val;
  18. else if(type=='C') vc+=val;
  19. else flag=1;
  20. }
  21. if(va>600||vb>600||vc>600)
  22. flag=1;
  23. sum1=va+vb+vc;
  24. if(sum1>1000)
  25. flag=1;
  26. if(!flag)
  27. sum[len++]=int(sum1*100);
  28. }
  29. memset(dp,sizeof(dp));
  30. for(i=0;i<len;i++)
  31. for(j=tt;j>=sum[i];j--)
  32. if(dp[j]<dp[j-sum[i]]+sum[i])
  33. dp[j]=dp[j-sum[i]]+sum[i];
  34. printf("%.2lf\n",1.0*dp[tt]/100);
  35. }
  36. return 0;
  37. }

猜你在找的VB相关文章