01背包是假多項式
背包容量超大時無法DP
只能用branch and bound
一般教科書上提到的剪枝的方法:
把物品依照CP值排序 CP值高的先放進去
用貪心法計算upper bound
upper bound比較大的點優先擴展
想請問各位大大
還有甚麼特別的方法可以加速嗎?
小弟在修演算法的課
卡一筆測資1000個物品 容量又超大
感謝

價值也超大嗎?

對啊有推薦類似的OJ題目嗎? 我查到的都還是一般的branchand bound

在搜尋前, 給予一個好的初始值, 而非在搜尋過程慢慢更新那麼有較好的初始值後, 總是先選與不選就要看測資的狀況有明顯差異

morris的意思是直接用upper bound很高的可行解下去暴搜嗎？可是如果最佳解其實在另一邊 會不會反而做白工啊？

聽起來很像是輝哥ㄉ課欸><

是喔 補考想把那筆測資過了

這一題收錄 批改娘 20005最後的測資我沒讓 bound and branch 的方式通過, 所以拿個 90 分不是問題著重還是在 upper bound 能算多快, 若每次從頭跑到尾那一種就太慢了

所以是 目前枚舉到第i項物品 剩餘空間w要事先建一個(i,w)的表嗎?會不會太大了XD

沒看到代碼，我不好說可能少哪一塊基礎但是當 n 破萬，你的直接搜會不會是 n^2 估算

我的code: http://codepad.org/ApC8XqWU所以目前討論有兩個改善的方向了1 從好一點的點開始 2 改善算上界的方法

首先，若全選為最佳解，這樣的總時間為 N^2搜尋空間太大，不應該牽涉到 priority queue直接使用一般的 DFS 搜尋，比較不會讓空間拖累時間

優先擴展上界較高的點不是比較好嗎？

估算總比預期來得好，意味著找到合法解後，仍有更多的狀態有待搜索，在這種情況空間需求將不切實際

單純好奇「容量又超大」具體是多少？

感謝各位 看起來是dfs就行了best first search 狀態太大時 每次都logn反而變瓶頸

輝哥的課嗎XD