題目描述：

現有一筆經費可以報銷一定額度的發票。允許報銷的發票類型包括買圖書（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

1 #include <iostream> 2 #include <cstdio> 3 #include <cstdlib> 4 #include <cmath> 5 #include <cctype> 6 #include <cstring> 7 8 #include <vector> 9 #include <deque> 10 #include <list> 11 #include <map> 12 #include <set> 13 #include <stack> 14 #include <queue> 15 #include <algorithm> 16 #include <string> 17 18 19 #define MAXD 99999999 20 using namespace std; 21 22 23 24 double re[40]; 25 26 int vis[40]; 27 28 29 double maxp; 30 31 32 33 int dfs(int v,double p,double q,int n) 34 { 35 36 if(p>q) 37 return 0; 38 39 if(p>maxp) 40 maxp=p; 41 42 43 int i; 44 for(i=0;i<n;i++) 45 { 46 if(vis[i]==0) 47 { 48 vis[i]=1; 49 dfs(i,p+re[i],q,n); 50 vis[i]=0; 51 } 52 } 53 54 return 0; 55 } 56 57 58 59 60 61 int main() 62 { 63 64 65 double q; 66 67 int n; 68 69 70 71 int i,j,k; 72 73 while(scanf("%lf%d",&q,&n)!=EOF) 74 { 75 if(n==0) 76 break; 77 78 k=0; 79 80 81 for(i=0;i<n;i++) 82 { 83 int m; 84 85 double sum=0; 86 87 88 scanf("%d",&m); 89 90 91 int tag=0; 92 93 for(j=0;j<m;j++) 94 { 95 char ty; 96 double p; 97 98 scanf(" %c:%lf",&ty,&p); 99 100 101 if(((ty=='A')||(ty=='B')||(ty=='C'))&&(tag==0)) 102 { 103 if(p<=600) 104 { 105 sum+=p; 106 } 107 else 108 { 109 tag=1; 110 } 111 } 112 else 113 {tag=1;} 114 115 116 117 } 118 119 120 if(tag==0) 121 { 122 123 if(sum<=1000) 124 { 125 re[k++]=sum; 126 } 127 } 128 } 129 130 131 for(i=0;i<k;i++) 132 { 133 vis[i]=0; 134 } 135 136 137 138 139 maxp=0; 140 141 142 dfs(0,0,q,k); 143 144 printf("%.2lf\n",maxp); 145 } 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 return 0; 168 }

?

轉載于:https://www.cnblogs.com/zjushuiping/archive/2012/05/30/2526831.html

總結

以上是生活随笔為你收集整理的最大报销额的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。