此題類似於 0-1 背包,但物品可以只拿走部分,因此不需要動態規劃,用貪心演算就可以解決。
解題思路 :
1. 先設一個可以讀取最大值的 priority_queue ( 存單位礦砂的價格 ),及一個變數 x = 0 ( 累積的價值 )
2. 因為本題的 m ( 1 < m < 100 )和 wi ( 1 < wi < 1000 )都很小,所以當輸入各種礦砂的個數 wi 及單位價值 pi 時,可以先在 priority_queue 中放入 wi 個 pi 。( 此時 priority_queue 最多只有 100000 個數 )
3. 持續用 top() 讀取最大值加到 x 中並彈出 ( 貪心法,選擇價值最高的礦砂 ),重複 n 次。但要注意當所有礦砂的取完時( 即 priority_queue 為空時 )停止取出,否則會因為彈空棧而發生 RE 的錯誤。