HDU 1684 最大报销额

2024-02-03 05:38

文章标签 最大 hdu 报销 1684

本文主要是介绍HDU 1684 最大报销额，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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位。

Sample Input

  200.00 3
2 A:23.50 B:100.00
1 C:650.00
3 A:59.99 A:120.00 X:10.00
1200.00 2
2 B:600.00 A:400.00
1 C:200.50
1200.50 3
2 B:600.00 A:400.00
1 C:200.50
1 A:100.00
100.00 0

Sample Output

  123.50
1000.00
1200.50

0—1背包，把每张发票当一个物品，其中，发票中有单项大于600的或者总额大于1000的，这张发票扔掉不要，也就是不加入物品的行列。整理出每张发票的总额，作为这件物品的价值也作为容量（相当于物品的体积），放到容量为q的背包中，这就是标准的0—1背包了；

转移方程:f[j]=max(f[j],f[j-1]+v[i]);

代码：

#include <stdio.h>
#include <string.h>
int max(int a,int b)
{if(a>b)return a;return b;
}
int dp[3000010];
int main()
{int n,i,j,m,flag,len;double q,val;int w[35];int w1[3];char ch;while (scanf("%lf%d",&q,&n)!=EOF&&n){memset(dp,0,sizeof(dp));len = 0;for (i=0;i<n;i++){scanf("%d",&m);flag = 1;for(j=0;j<3;j++)w1[j] = 0;j = 0;while (m--){getchar();scanf("%c:%lf",&ch,&val);if(ch>='A'&&ch<='C'){j = ch-'A';w1[j]+=(int)(val*100);}/*不可报销条件*/if(w1[j]>60000||w1[0]+w1[1]+w1[2]>100000||ch!='A'&&ch!='B'&&ch!='C')flag = 0;}if (flag)w[len++] = w1[0]+w1[1]+w1[2];}for (i=0;i<len;i++){for (j=(int)(q*100);j>=w[i];j--)dp[j] = max(dp[j],dp[j-w[i]]+w[i]);}printf("%.2lf\n",(double)(dp[(int)(q*100)]/100.0));}return 0;
}

这篇关于HDU 1684 最大报销额的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！