1025_最大报销额

2019-11-10 18:54:28

字体：大中小

来源：转载

供稿：网友

// 1025_最大报销额.cpp : 定义控制台应用程序的入口点。//题目1025：最大报销额//时间限制：1 秒内存限制：32 兆特殊判题：否提交：4936解决：1184//题目描述：// 现有一笔经费可以报销一定额度的发票。允许报销的发票类型包括买图书（A类）、文具（B类）、差旅（C类），要求每张发票的总额不得超过1000元，每张发票上，单项物品的价值不得超过600元。现请你编写程序，在给出的一堆发票中找出可以报销的、不超过给定额度的最大报销额。//输入：// 测试输入包含若干测试用例。每个测试用例的第1行包含两个正数 Q 和 N，其中 Q 是给定的报销额度，N（N<=30）是发票张数。随后是 N 行输入，每行的格式为：// m Type_1:PRice_1 Type_2:price_2 ... Type_m:price_m// 其中正整数 m 是这张发票上所开物品的件数，Type_i 和 price_i 是第 i 项物品的种类和价值。物品种类用一个大写英文字母表示。当N为0时，全部输入结束，相应的结果不要输出。//输出：// 对每个测试用例输出1行，即可以报销的最大数额，精确到小数点后2位。//样例输入：//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//样例输出：//123.50//1000.00//1200.50//来源：//2007年浙江大学计算机及软件工程研究生机试真题#include "stdafx.h"#include "stdio.h"#include "iostream"#include "string"#include "string.h"using namespace std;int sum[35];int dp[1000000];int main(){ double Q; int N; while(cin>>Q>>N&&N){ int cursor = 1; for(int j = 0;j<N;j++){ int m; cin>>m; char a,type,b; //空格，类型，冒号 double price; //报销金额 double temp_sum = 0.00; //一张发票所要报销的金额总和 int flag = 0; for(int i = 0;i<m;i++){ scanf("%c%c%c%lf",&a,&type,&b,&price); if(!flag){ temp_sum += price; if(type!='A' && type!='B' && type!='C') flag = 1; else if(price>600.00 || price>Q) flag = 1; else if(temp_sum>1000.00) flag = 1; } } if(!flag){ sum[cursor++] = (int)(temp_sum * 100); } } memset(dp,0,sizeof(dp)); for(int i = 1;i<cursor;i++) for(int j = (int)(Q * 100);j>=sum[i];j--){ dp[j] = max(dp[j - sum[i]]+sum[i],dp[j]); } printf("%.2lf/n",dp[(int)(Q*100)]/100.00); } return 0;}/*1.这题背包问题求的数值是double而不是int型的，由于精度是小数点后两位，所以应该统一 *100，结果再除100;*/

上一篇：2、关键字auto、static、register的精华

下一篇：STM32L152 STOP模式

学习交流

索泰发布一款GTX 1070 Mini迷你版本:小机

索泰发布一款GTX 1070 Mini迷你版本:小机箱大爱...

热门图片

猜你喜欢的新闻

猜你喜欢的关注