#45250: 解題方法


lbm00138 (A是蘋果 B是香蕉)

學校 : 臺北市立成淵高級中學
編號 : 270386
來源 : [1.164.226.154]
最後登入時間 :
2025-02-05 08:56:58
p500. 礦沙背包問題 -- 板橋高中教學題 | From: [61.71.41.184] | 發表日期 : 2025-02-02 00:32

此題類似於 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 的錯誤。

 

https://hackmd.io/@-NK1yL0aSQS4GGo6S9IfeQ/SJKavTodkx

 
ZeroJudge Forum