01背包是假多項式
背包容量超大時無法DP
只能用branch and bound
一般教科書上提到的剪枝的方法:
把物品依照CP值排序 CP值高的先放進去
用貪心法計算upper bound
upper bound比較大的點優先擴展
想請問各位大大
還有甚麼特別的方法可以加速嗎?
小弟在修演算法的課
卡一筆測資1000個物品 容量又超大
感謝
作者:
oToToT (å±å©)
2019-12-11 19:17:00價值也超大嗎?
對啊有推薦類似的OJ題目嗎? 我查到的都還是一般的branchand bound
作者: Morris1028 (某 M) 2019-12-12 06:43:00
在搜尋前, 給予一個好的初始值, 而非在搜尋過程慢慢更新那麼有較好的初始值後, 總是先選與不選就要看測資的狀況有明顯差異
morris的意思是直接用upper bound很高的可行解下去暴搜嗎？可是如果最佳解其實在另一邊 會不會反而做白工啊？
作者:
Hsins (翔)
2019-12-12 18:49:00聽起來很像是輝哥ㄉ課欸><
作者: Morris1028 (某 M) 2019-12-12 20:06:00
這一題收錄 批改娘 20005最後的測資我沒讓 bound and branch 的方式通過, 所以拿個 90 分不是問題著重還是在 upper bound 能算多快, 若每次從頭跑到尾那一種就太慢了
所以是 目前枚舉到第i項物品 剩餘空間w要事先建一個(i,w)的表嗎?會不會太大了XD
作者: Morris1028 (某 M) 2019-12-12 20:56:00
沒看到代碼，我不好說可能少哪一塊基礎但是當 n 破萬，你的直接搜會不會是 n^2 估算
作者: Morris1028 (某 M) 2019-12-12 21:24:00
首先，若全選為最佳解，這樣的總時間為 N^2搜尋空間太大，不應該牽涉到 priority queue直接使用一般的 DFS 搜尋，比較不會讓空間拖累時間
作者: Morris1028 (某 M) 2019-12-13 07:56:00
估算總比預期來得好，意味著找到合法解後，仍有更多的狀態有待搜索，在這種情況空間需求將不切實際
作者:
c910335 (達人)
2019-12-15 06:48:00單純好奇「容量又超大」具體是多少？
感謝各位 看起來是dfs就行了best first search 狀態太大時 每次都logn反而變瓶頸
作者:
kyrie77 (NTU KI)
2018-02-28 21:07:00輝哥的課嗎XD