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

代码

#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;
}

猜你在找的VB相关文章