Problems | Status | Rank | Forum | Contest

回分類題庫
d637: 路過的鴨duck
關鍵字： jack1

Difficulity ： 3 | 測資點： 3 ( 公開 ) | 評分方式： Tolerant Judge
Accepted ： 48 Users /64 Times | Submit : 56 Users /107 Times | Accepted rate : 86%
每個測資點 Time Limit依序為： 1s 1s 1s | Memory Limit : 64MBytes
最近更新 : 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 ：help

若題目沒有特別說明，則應該以多測資的方式讀取，若不知如何讀取請參考 a001 的範例程式。
6
10 8
25 25
65 75
25 29
25 17
15 20

Sample Output ：

112

Hint ：

1.0/1背包問題，動態規劃法，DynamicPrograming(DP)
2.共三個測資點30%、35%、35%，
第一個測資點即範例測資。

Author ：

jack1 (管理員：jack1)

Solve it! Status Forum Rank


Powered by ZeroJudge R1.3 Built0817