d637: 路過的鴨duck
Tags : DP
Accepted rate : 1124人/1218人 ( 92% ) [非即時]
評分方式:
Tolerant

最近更新 : 2010-01-30 10:22

Content
有一天
有一隻路過的鴨duck

牠…太餓結果就死了囧…

當他到天國的時候,
遇到了先前駕崩的鴨子王(duck king),
牠變成了管理鴨子靈魂的神(duck king god,簡稱duckingod)

duckingod生前是一隻非常聰明的神鴨,
所以duckingod給這隻路過的鴨一個復活的機會。
給牠一袋鴨飼料,裡面的每顆飼料有不同的體積和飽足感
只要路過的鴨能夠在有限的食量內吃得最飽,
那牠就能復活了!

快寫個程式幫幫路過的鴨吧!呱呱呱!
Input
每個測資點僅一組測資,不必EOF讀檔。
第一行有正整數n(1<n<=10000)表示有n顆鴨飼料
接下來的n行,每行有ab兩個正整數,
a代表這顆鴨飼料的體積,b代表飽足感(1<=a<=100 , 1<=b<=5000)
並且鴨子最多可以吃滿100體積的飼料。
Output
請輸出這袋鴨飼料能帶給路過的鴨的最大飽足感!
Sample Input #1
6
10 8
25 25
65 75
25 29
25 17
15 20
Sample Output #1
112
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (30%): 1.0s , <1K
公開 測資點#1 (35%): 1.0s , <1M
公開 測資點#2 (35%): 1.0s , <1M
Hint :
1.0/1背包問題,動態規劃法,DynamicPrograming(DP)
2.共三個測資點30%、35%、35%,
第一個測資點即範例測資。
Tags:
DP
出處:
jack1 [管理者:
jack1 (我是韜哥我忘了拿通知單)
]


ID User Problem Subject Hit Post Date
25437
chuan53 (eggMan)
d637
b184
195 2021-05-21 17:24
22819
fire5386 (fffelix)
d637
解題演算法
569 2020-10-04 21:27