a455.
TOI2010 第四題：商品特賣問題
Content
在一個年終大拍賣活動中，一家迪化街的商店推出了一個特賣活動，老闆說只要你花錢買4個箱子，第一個箱子最多可裝30公斤的商品，第二個箱子最多可裝40公斤的商品，第三個箱子最多可裝50公斤的商品，第四個箱子最多可裝25公斤的商品。可以挑選的商品有十種，重量分別是15, 16, 30, 18, 19, 20, 21, 25, 24, 及17公斤。每一種商品最多只能挑一次，且一種商品不可拆開分到不同箱子中。假設產品加總的重量小於等於箱子的限定重量就一定裝得下這些產品，由於每樣產品的售價一樣，因此若挑選能裝入4個箱子的商品種類愈多，便表示價值愈高。請你寫一個程式來算出最多可以裝入這些箱子的商品數目，以便估算是否划算。
Input
第一行為兩個整数M及N以空白區分，其中M表示箱子的個數，而N表示商品的種類數。
第二行開始的M行各為每一個箱子可容納的最大重量(公斤)。從第M+2行開始的N行，則分別表示N種商品個別的重量(公斤) 。
其中0<M≤50，0<N≤1000。
Output
顯示最多能够裝入這些箱子的商品數目。若找不到能裝入這些箱子的商品，請輸出0。
Sample Input
#1
範例一： 4 10 30 40 50 25 15 16 30 18 19 20 21 25 24 17 範例二： 3 9 20 10 10 3 8 3 7 9 3 5 8 5
Sample Output
#1
範例一： 7 範例二： 7
測資資訊：
記憶體限制：
512
MB
公開 測資點#0 (20%): 10.0s , <1K
公開 測資點#1 (20%): 10.0s , <1K
公開 測資點#2 (20%): 10.0s , <1K
公開 測資點#3 (20%): 10.0s , <1K
公開 測資點#4 (20%): 10.0s , <1M
公開 測資點#0 (20%): 10.0s , <1K
公開 測資點#1 (20%): 10.0s , <1K
公開 測資點#2 (20%): 10.0s , <1K
公開 測資點#3 (20%): 10.0s , <1K
公開 測資點#4 (20%): 10.0s , <1M
Hint ：
時限仿照原題，更改為10秒。 (2012/7/6 修改)
Tags:
| ID | User | Problem | Subject | Hit | Post Date |
| 41597 |
|
a455 | 46 | 2024-08-09 12:08 |