d637: 路過的鴨duck

出處

http://zerojudge.tw/ShowProblem?problemid=d637

內容 ：

有一天

有一隻路過的鴨duck

牠…太餓結果就死了囧…

當他到天國的時候，

遇到了先前駕崩的鴨子王(duck king)，

牠變成了管理鴨子靈魂的神(duck king god，簡稱duckingod)

duckingod生前是一隻非常聰明的神鴨，

所以duckingod給這隻路過的鴨一個復活的機會。

給牠一袋鴨飼料，裡面的每顆飼料有不同的體積和飽足感

只要路過的鴨能夠在有限的食量內吃得最飽，

那牠就能復活了！

快寫個程式幫幫路過的鴨吧！呱呱呱！

輸入說明 ：

每個測資點僅一組測資，不必EOF讀檔。

第一行有正整數n(1<n<=10000)表示有n顆鴨飼料

接下來的n行，每行有ab兩個正整數，

a代表這顆鴨飼料的體積，b代表飽足感(1<=a<=100 , 1<=b<=5000)

並且鴨子最多可以吃滿100體積的飼料。

輸出說明 ：

請輸出這袋鴨飼料能帶給路過的鴨的最大飽足感！

範例輸入 ：

6

10 8

25 25

65 75

25 29

25 17

15 20

範例輸出 ：

112

提示 ：

背景知識： DP

1.0/1背包問題，動態規劃法，DynamicPrograming(DP)

2.共三個測資點30%、35%、35%，

第一個測資點即範例測資。

出處 ：

jack1 (管理：jack1)

解題策略

0-1 knapsack