題目連結(jié):
題目大意:
輸入第一列給定一正整數(shù) n (1 ≦ n ≦ 10000),代表有 n 顆飼料。接著有 n 列輸入,每列給定兩正整數(shù) a 、 b (1 ≦ a ≦ 100 , 1 ≦ b ≦ 5000),代表每顆飼料的體積以及飽足感。
已知 duck 最多可以吃 100 單位體積的飼料。試問 duck 最多可以獲得多少飽足感?
範(fàn)例輸入:
6
10 8
25 25
65 75
25 29
25 17
15 20
範(fàn)例輸出:
112
解題思維:
典型的 01 背包問題(01 Knapsack Problem),參見
這題。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。