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


rollfc (胖胖貓)

學校 : 國立清華大學
編號 : 81012
來源 : [36.229.32.12]
最後登入時間 ：
2024-04-29 00:29:15
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.229.32.12]
最後登入時間 ：
2024-04-29 00:29:15
c824. 第六題：背包問題 EX -- 107學年度高雄市資訊學科能力競賽複賽 | From: [36.226.96.168] | 發表日期 : 2019-03-02 04:55

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

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

 
ZeroJudge Forum