b184: 5. 裝貨櫃問題
Tags : DP
Accepted rate : 487人/503人 ( 97% ) [非即時]
評分方式:
Tolerant

最近更新 : 2008-11-10 11:12

Content

現在一共有若干項貨品可選擇運載,每一項k都有一個已知的體積v[k],以及載運的利潤c[k],但是貨櫃的總容量是100,可能無法將貨物全部裝入,希望選出其中的若干項,其體積總和不超過100,使得利潤最大。(每一項貨物的體積為1~100 的整數,而利潤是1~60000 的整數。)

Input

 第一行是貨品數量,接下來每行各有兩筆數據,第一筆代表各項貨物的體積,第二筆代表各項貨物的利潤。

Output

輸出最大的利潤,例如輸出一、二項:第一項貨物的體積為30,利潤為60,第二項貨物的體積為20,利潤為50

Sample Input
4
30 60
20 50
35 40
60 70
10
80 88 
33 66 
13 26
77 150
95 195
45 90
8 16
20 41
40 13
68 20
Sample Output
150
198
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (100%): 1.0s , <1K
Hint :
Tags:
DP
出處:
97學年度高雄市資訊學科能力競賽 [管理者:
khps9703 (khps)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」