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


rollfc (胖胖貓)

學校 : 國立清華大學
編號 : 81012
來源 : [36.226.228.108]
最後登入時間 ：
2025-10-12 02:18:22
c824. 第六題：背包問題 EX -- 107學年度 高雄市 資訊學科能力競賽 複賽
| From: [140.113.208.181] | 發表日期: 2018-11-26 18:54

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

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

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


yllan (yllan)

學校 : 不指定學校
編號 : 92998
來源 : [220.135.204.244]
最後登入時間 ：
2021-12-09 10:13:44
c824. 第六題：背包問題 EX -- 107學年度 高雄市 資訊學科能力競賽 複賽
| From: [223.137.181.236] | 發表日期: 2019-02-27 20:20

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

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


這是包裝成背包問題的greedy

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

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


rollfc (胖胖貓)

學校 : 國立清華大學
編號 : 81012
來源 : [36.226.228.108]
最後登入時間 ：
2025-10-12 02:18:22
c824. 第六題：背包問題 EX -- 107學年度 高雄市 資訊學科能力競賽 複賽
| From: [36.226.96.168] | 發表日期: 2019-03-02 04:55

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

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

ZeroJudge Forum