HDU 1864 最大报销额 0-1背包

题意

现有一笔经费可以报销一定额度的发票。允许报销的发票类型包括买图书（A类）、文具（B类）、差旅（C类），要求每张发票的总额不得超过1000元，每张发票上，单项物品的价值不得超过600元。现请你编写程序，在给出的一堆发票中找出可以报销的、不超过给定额度的最大报销额。

这里要注意的是，只要总金额大于1000，或者每种类别的总金额大于600，或者这个发票中有其他类别物品，就不能报销

解题思路

这里就是简单的\(0-1\)背包了，主要的就是在于对于数据的预处理方面。

还有一点就是数组下标需要整数，但是这个金额都是浮点数，该怎么办呢？我们发现，这里输入的数据都是保留了小数点后两位，所以我们可以对每个金额\(*100\)，这样的话就都是整数了。

一些细节参见代码实现。

代码实现

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int maxn=40;

const int maxm=4e5+7;

const int maxq=1000*30*100+7;

double rec[maxn];

double dp[maxq];

double q;

int n, m;

int main()

{

	while(scanf("%lf%d", &q, &n) && n!=0)

	{

		char type;

		int flag, cnt=0; //使用cnt来记录实际合法的发票个数

		while(n--)

		{

			double price, va=0, vb=0, vc=0;//总金额，A，B，C类的总金额

			flag=1; //一个标记

			scanf("%d", &m);

			while(m--)

			{

				scanf(" %c:%lf", &type, &price);

				if(flag==0)//如果标记为0的话，说明前面有不合法的数据，这个发票也就作废了

					continue;

				if(type=='A')

					va+=price;

				else if(type=='B')

					vb+=price;

				else if(type=='C')

					vc+=price;

				else flag=0;

			}

            //下面会再次进行判断

			if(flag==1 && va<=600.0 && vb<=600.0 && vc<=600.0 && (va+vb+vc)<=1000.0)

			{

				rec[++cnt]=va+vb+vc;

			}

		}

		memset(dp, 0, sizeof(dp));

		int max_val=int(q*100);//最大金额化成整数

		for(int i=1; i<=cnt; i++)

		{

			for(int j=max_val; j>=int(rec[i]*100); j--) //每张发票的金额也要化成整数

			{

				dp[j]=max(dp[j-int(rec[i]*100)]+rec[i], dp[j]);

			}

		}

		printf("%.2lf\n", dp[max_val]);//注意输出格式，要求小数点后两位。

 	}

 	return 0;

}