1025_最大報銷額

2019-11-10 19:04:19

字體：大中小

來源：轉載

供稿：網友

// 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;*/

上一篇：關于神經網絡歸一化方法的整理

下一篇：MySQL索引