#22617: 背包非背包


p3a_owhj (阿普二信)

學校 : 不指定學校
編號 : 39897
來源 : [36.227.79.178]
最後登入時間 :
2024-06-04 22:09:36
c835. 第六題:背包問題 -- 2018資訊學科能力競賽高中組高雄市 | From: [36.225.44.28] | 發表日期 : 2020-09-20 02:46

題目說是背包問題,但不知道可使用 什麼「變形」方式的背包 可解,好像會 TLE吧

但 2^0+2^1+...+2^m-1 < 2^m
若將重量的級數看成 0~m級,每次將最小的兩個同級價值合併,  重量升一級,當到達m級時,價值最大的 m級就是答案了

我是用 priority_queue 實作的,勉強 AC

另最後一個測資 > 9*10^9

 
#22632: Re:背包非背包


asnewchien@gmail.com (david)

學校 : 不指定學校
編號 : 68108
來源 : [122.117.95.179]
最後登入時間 :
2024-11-04 20:21:51
c835. 第六題:背包問題 -- 2018資訊學科能力競賽高中組高雄市 | From: [122.118.83.198] | 發表日期 : 2020-09-21 02:15

感謝您的想法,

應該不必使用 priority_queue

只要把每個等級的值排序後兩兩相加,丟到下一級即可。

 
#41088: Re: 背包非背包


seancai78@gmail.com (風月春秋)

學校 : 臺北市立成功高級中學
編號 : 176406
來源 : [140.113.124.212]
最後登入時間 :
2024-10-07 23:20:19
c835. 第六題:背包問題 -- 2018資訊學科能力競賽高中組高雄市 | From: [118.166.21.122] | 發表日期 : 2024-07-02 17:37

另最後一個測資 > 9*10^9


超級感謝測資提示,不然我不知道甚麼時候才能發現

 
ZeroJudge Forum