http://ac.jobdu.com/problem.php?pid=1025 最大报销额
//将题目中数字都扩大100倍变成整数,就可看作经典的01背包问题
//设报销额度为背包上限,可报销支票金额为价格,可报销支票金额为重量
//a[]存的既是价格,又是重量
#include<iostream>
#include<cstdio>
using namespace std;
int a[32]; //存的既是价格,又是重量
const int MAX = 3000005;
int f[MAX];
int V; //背包的体积
void ZeroOnePack(int cost, int weight)
{
int v;
for (v = V; v >= cost; v--)
f[v] = f[v] > (f[v - cost] + weight) ? f[v] : (f[v - cost] + weight);
}
int main(void)
{
int i,j,n,m,k,flag;
double q,price,A,B,C;
char type;
while(scanf("%lf %d",&q,&n)!=EOF)
{
if(!n)
break;
k=0;
for(i=0;i<n;i++)
{
scanf("%d",&m);
A=B=C=0;
flag=0;
for(j=0;j<m;j++)
{
getchar();
scanf("%c:%lf",&type,&price);
if(type=='A')
A+=price;
else if(type=='B')
B+=price;
else if(type=='C')
C+=price;
else
flag=1;
}
if(!flag)
{
if(A+B+C<=1000 && A<=600 && B<=600 && C<=600) //合法的发票
a[k++]=(int)(100*(A+B+C));
}
}
V=q*100;
for(i=0;i<=V;i++) //没有要求把背包装满
{
f[i]=0;
}
for(i=0;i<k;i++)
ZeroOnePack(a[i],a[i]);
printf("%.2lf\n",f[V]/100.0);
}
return 0;
}
分享到:
相关推荐
2011年浙江大学计算机及软件工程机试真题2011年浙江大学计算机及软件工程机试真题2011年浙江大学计算机及软件工程机试真题
计算机软考中级软件设计师历年真题与解析汇总(2004_2019全年所有试题及答案)
2007年上半年软件设计师真题与解析,2007年5月软件设计师真题解析
软件设计师考试考点分析与真题详解(计算机与软件工程知识篇)
2007年下半年软件设计师试题 Word版 2007年下半年软考网络工程师试题 Word版 2007年下半年数据库系统工程师试题 Word版 2007年下半年网络管理员试题 Word版 2007年下半年系统分析师试题 Word版 2007年下半年信息处理...
专转本2007年计算机真题专转本2007年计算机真题专转本2007年计算机真题
郑州大学计算机专业历年复试专业课真题,408专业,944专业 软件工程专业复试真题 郑州大学英语复试题目
北邮计算机院软件工程期末复习真题 北邮计算机院软件工程期末复习真题
文件包含了长安大学考研历年真题,且有上千题题库,包含软件工程所有内容,适用于研究生考试和本科期末考试,以及其他考试练习。
软考中级软件设计师历年真题
2007年下半年软件设计师真题与解析,2007年11月软件设计师真题解析
西北大学软件工程10-19年考研真题
2022年11月软考中级软件设计师真题及答案解析下午案例分析真题及答案解析
计算机专业软件考试历年真题(数据库系统工程师),大概包含了04——08的真题,因为刚考完,分享一下
包括软考的上午和下午试题及真题分析。
软件工程造价师试题解析,根据日常老师讲解和试题分享进行了总结
中科大计算机+软件工程考研 408真题及答案,从09~17年 答案超详细
软件设计师考试_历年真题及答(2007年-2012)年