回分類題庫
b030: 隨選視訊
關鍵字: 動態規劃-01背包問題

測資點 : 5 | Time Limit : 1000 ms | Memory Limit : 32000 KB
Accepted : 792 Times / 599 Users | Submit : 2269 Times / 659 Users | Accepted rate : 91%
題目加入時間 : 2011-10-31 08:14

Content: 简体中文

小綠購買了某線上影視公司提供的隨選視訊方案,只要付一筆費用,就可以觀看總長度 M 分鐘的影片,小綠從該公司提供的影片中挑選了 N 部有興趣的電影,每部電影都有不同的長度以及滿足感,請問你小綠該如何選擇,才能得到最大的滿足感。挑選影片的限制如下:

  1. 影片一定要從頭看到尾,只看一半得不到任何的滿足感。 
  2. 同一部影片只需要看一次,看兩次以上滿足感並不會增加。
  3. 影片的觀賞順序並不會影響它們的滿足感。

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 :

12

Hint :

Author :

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

  Solve it!   Status Forum