發表新討論
#16139: 關於這一題的解題方向


rollfc (點石學園 StoneCampus)

c824. 第六題：背包問題 EX -- 107學年度 高雄市 資訊學科能力競賽 複賽 | From: [140.113.208.181] | 發表日期: 2018-11-26 18:54

雖然知道物品重量設定成2的次方項，應該和背包的更新方式有關

但是不知道從何下手，希望解開的大大能提示

#17003: Re:關於這一題的解題方向


yllan (yllan)

c824. 第六題：背包問題 EX -- 107學年度 高雄市 資訊學科能力競賽 複賽 | From: [223.137.181.236] | 發表日期: 2019-02-27 20:20

雖然知道物品重量設定成2的次方項，應該和背包的更新方式有關

但是不知道從何下手，希望解開的大大能提示


這是包裝成背包問題的greedy

類似binomial heap那樣，把兩個重量為2的物品合併成一個重量為4的物品就可以了

#17044: Re:關於這一題的解題方向


rollfc (點石學園 StoneCampus)

c824. 第六題：背包問題 EX -- 107學年度 高雄市 資訊學科能力競賽 複賽 | From: [36.226.96.168] | 發表日期: 2019-03-02 04:55

感謝大大的提點，已順利AC。

想問一下與PTT留言的大大是同一位嗎？

ZeroJudge Forum