一、原题
B - 最大报销额
Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u
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
二、题目大意:
现在给你Q的指定报销额,以及N张发票,每张发票有m个物品以及其相对应的物品额。
符合要求的发票应满足:
1.每件物品总额不超过600(A<=600&&B<=600&&C<=600)
2.每张发票总额不超过1000(A+B+C<=1000)
3.发票中不可含除ABC以外的物品。
该题可将每张符合要求的发票看做一个物品(V[i]=W[i]=每张发票总额),发票总额度Q看做背包容量;
由于保留小数点后两位,可*100,转化为标准01背包
三、基本思路:
1、整型与浮点型的几次转换
①输入的每个pri_tmp,乘100.0后转化为整数
price=int(pri_tmp*100.0)
②进入DP后便于操作将Q(总额度)转化为int型
int Q_tmp=int(Q*100.0);
③输出时再将结果转化为浮点型(这里dp的类型原为int)
double ans=dp[Q_tmp]/100.0;
Ps:这里除了price_tmp,Q,ans是浮点型以外,其他全是int型;
2、检验发票是否可用,bool flag
if(A>60000||B>60000||C>60000||!flag||A+B+C>100000)
{
flag=false;
continue;//不符合题意进入下一张发票
}
3、主要的变量:
int fapiao[NUM];//每张可用发票的额度
int dp[VMAX];//dp[v]表示v的容量最多装多大价值
Ps:VMAX定义为3000010而不是30010,主要是因为要乘以100啊!!!
4、 DP关键部分函数
状态转移方程:dp[j]=max(dp[j],(dp[j-fapiao[i]]+fapiao[i]))//这里V=W。前一个fapiao[i]表示V[i],后一个fapiao[i]表示W[i]
for(int i=0;i<fa_num;i++)
for(int j=Q_tmp;j>=fapiao[i];j--)
dp[j]=max(dp[j],(dp[j-fapiao[i]]+fapiao[i]));//dp[v]表示v的容量最多装多大价值
四、源码完整版
#include <iostream>
#include <cstdio>
#include <cstring>
#define NUM 40
#define VMAX 3000010//刚开始这里定义为30010,死掉了啊。。。。每个数字都要乘以100的啊!!!
using namespace std;
int fapiao[NUM];
int dp[VMAX];
double max(double a,double b)
{
return a>b?a:b;
}
int main()
{
///freopen("in.txt","r",stdin);
double Q;
int N;
while(cin>>Q>>N&&N)
{
memset(fapiao,0,sizeof(fapiao));
memset(dp,0,sizeof(dp));
int fa_num=0;
while(N--)
{
int m;
cin>>m;
int A=0,B=0,C=0;//该张发票上的ABC总额
bool flag=true;//表示该张发票可用
while(m--)
{
char ch;
double pri_tmp;
int price;
cin>>ch;
cin.get();//接受“:”
cin>>pri_tmp;
price=int(pri_tmp*100.0);
switch(ch)
{
case 'A':A+=price;break;
case 'B':B+=price;break;
case 'C':C+=price;break;
default: flag=false;//出现非法字符发票不可用
}
}
//对于每张发票,检验其是否可用
if(A>60000||B>60000||C>60000||!flag||A+B+C>100000)
{
flag=false;
continue;//不符合题意进入下一张发票
}
else
fapiao[fa_num++]=A+B+C;//若发票可用则存入数组
}
//DP
int Q_tmp=int(Q*100.0);
for(int i=0;i<fa_num;i++)
for(int j=Q_tmp;j>=fapiao[i];j--)
dp[j]=max(dp[j],(dp[j-fapiao[i]]+fapiao[i]));//dp[v]表示v的容量最多装多大价值
double ans=dp[Q_tmp]/100.0;
printf("%.2f\n",ans);
}
return 0;
}
PS:初涉01背包。。。。。。。不懂装懂一下伐。。。。其实感觉有的时候不需要全懂,这有点像《黑客与画家》的作者的观点。。太难的东东,先会80%,写着写着就慢慢明白了。。否则只怕会被难题压倒吧。。。
另,附上链接:
http://acm.hdu.edu.cn/showproblem.php?pid=1864