回分類題庫
b031: 吃到飽餐廳
關鍵字: 動態規劃-無窮背包問題

測資點 : 5 | Time Limit : 1000 ms | Memory Limit : 32000 KB
Accepted : 721 Times / 579 Users | Submit : 1223 Times / 597 Users | Accepted rate : 97%
題目加入時間 : 2011-10-31 08:14

Content: 简体中文

小筑是位很瘦的女生,即使如此,她的食量可是很驚人的。今天,小筑走進一間吃到飽餐廳,因為費用不便宜,所以她決定要儘量把它吃回本。餐廳裡有 N 種食物,每一種食物有它不同的份量以及價值,因為小筑是很環保的,所以她絕對不會把食物只吃一半,而且如果吃不下某樣食物,她就不會去吃,請問你小筑最多可以吃下多少價值的食物。

Input:

第一行有兩個正整數 N、M (1<=N<=100、1<=M<=1000),N 為餐廰的食物有幾種,M 為小筑的食量。接下來有 N 行食物的資料,每行有兩個正整數 L、S (1<=L<=100、1<=S<=500),L 為該食物的份量,S 為該食物的價值。

Output:

請輸出以 M 為最大食量時,小筑所吃的食物的最大價值是多少。

Sample Input:help

若題目沒有特別說明,則應該以多測資的方式讀取,若不知如何讀取請參考 a001 的範例程式。
4 9
2 3
3 4
4 5
5 6

Sample Output :

13

Hint :

Author :

動態規劃-無窮背包問題 (管理員:sagit)

  Solve it!   Status Forum