b184: 5. 裝貨櫃問題
標籤 : DP
通過比率 : 97% (451 人 / 466 人 ) (非即時)
評分方式:
Tolerant

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

內容

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

輸入說明

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

輸出說明

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

範例輸入
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
範例輸出
150
198
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (100%): 1.0s , <1K
提示 :
標籤:
DP
出處:
97學年度高雄市資訊學科能力競賽 [編輯:
khps9703 (khps)
]


編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」