蘇世機試小課堂，考研機試不再慌！

公主號：蘇世學社考研? 蘇世計算機考研

最大報銷額

題目描述

現(xiàn)有一筆經(jīng)費可以報銷一定額度的發(fā)票。允許報銷的發(fā)票類型包括買圖書（A類）、文具（B類）、差旅（C類），要求每張發(fā)票的總額不得超過1000元，每張發(fā)票上，單項物品的價值不得超過600元?，F(xiàn)請你編寫程序，在給出的一堆發(fā)票中找出可以報銷的、不超過給定額度的最大報銷額。

輸入描述

測試輸入包含若干測試用例。每個測試用例的第1行包含兩個正數(shù) Q 和 N，其中 Q 是給定的報銷額度，N（N<=30）是發(fā)票張數(shù)。隨后是 N 行輸入，每行的格式為：

m Type_1:price_1 Type_2:price_2 ...Type_m:price_m

其中正整數(shù) m 是這張發(fā)票上所開物品的件數(shù)，Type_i 和 price_i 是第 i 項物品的種類和價值。物品種類用一個大寫英文字母表示。當N為0時，全部輸入結(jié)束，相應的結(jié)果不要輸出。

輸出描述

對每個測試用例輸出1行，即可以報銷的最大數(shù)額，精確到小數(shù)點后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

答案

①讀題:

發(fā)現(xiàn)這個題是給出報銷額度、每張發(fā)票上購買的物品和價格，找出可以報銷的最大價格。

②想出思路：

0-1背包問題

③動手編程：

④測試樣例：

⑤提交代碼：

進入下面的鏈接提交代碼（或點擊閱讀原文）

https://www.nowcoder.com/practice/8ec050ca75d343cfb45a305f5a7baa73?tpId=40&&tqId=21465&rp=1&ru=/ta/kaoyan&qru=/ta/kaoyan/question-ranking

⑥返回評測結(jié)果：

至此，這道題我們就已經(jīng)完成了。

0-1背包問題，在這里需要注意輸入一張發(fā)票上的物品種類和價值可能不合法，所以需要判斷，同時將一張發(fā)票的總價值×1000，轉(zhuǎn)化成整數(shù)存入數(shù)組中。

蘇世學社旗下品牌，專注于計算機考研

計算機考研一手資訊，原創(chuàng)高質(zhì)量干貨

深度的學習分享丨咨詢前輩丨個性化指導