主題

ZeroJudge - d637: 路過的鴨duck 解題心得

Not In My Back Yard | 2021-02-05 00:00:04 | 巴幣 0 | 人氣 41

題目連結:


題目大意:
輸入第一列給定一正整數 n (1 ≦ n ≦ 10000),代表有 n 顆飼料。接著有 n 列輸入,每列給定兩正整數 a 、 b (1 ≦ a ≦ 100 , 1 ≦ b ≦ 5000),代表每顆飼料的體積以及飽足感。

已知 duck 最多可以吃 100 單位體積的飼料。試問 duck 最多可以獲得多少飽足感?



範例輸入:
6
10 8
25 25
65 75
25 29
25 17
15 20


範例輸出:
112


解題思維:
典型的 01 背包問題(01 Knapsack Problem),參見這題




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作