→ oToToT: 價值也超大嗎? 12/11 19:17
→ s89162504: 對啊 12/11 19:22
→ s89162504: 有推薦類似的OJ題目嗎? 我查到的都還是一般的branch 12/11 19:23
→ s89162504: and bound 12/11 19:23
推 Morris1028: 在搜尋前, 給予一個好的初始值, 而非在搜尋過程慢慢 12/12 06:43
→ Morris1028: 更新 12/12 06:43
推 Morris1028: 那麼有較好的初始值後, 總是先選與不選就要看測資的 12/12 06:55
→ Morris1028: 狀況有明顯差異 12/12 06:55
→ s89162504: morris的意思是直接用upper bound很高的可行解下去暴搜 12/12 16:47
→ s89162504: 嗎？ 12/12 16:47
→ s89162504: 可是如果最佳解其實在另一邊 會不會反而做白工啊？ 12/12 16:48
→ Hsins: 聽起來很像是輝哥ㄉ課欸>< 12/12 18:49
→ s89162504: 是喔 補考想把那筆測資過了 12/12 19:45
→ Morris1028: 這一題收錄 批改娘 20005 12/12 20:06
→ Morris1028: 最後的測資我沒讓 bound and branch 的方式通過, 所 12/12 20:08
→ Morris1028: 以拿個 90 分不是問題 12/12 20:08
→ Morris1028: 著重還是在 upper bound 能算多快, 若每次從頭跑到尾 12/12 20:25
→ Morris1028: 那一種就太慢了 12/12 20:25
→ s89162504: 所以是 目前枚舉到第i項物品 剩餘空間w 12/12 20:33
→ s89162504: 要事先建一個(i,w)的表嗎? 12/12 20:34
→ s89162504: 會不會太大了XD 12/12 20:37
推 Morris1028: 沒看到代碼，我不好說可能少哪一塊基礎 12/12 20:56
→ Morris1028: 但是當 n 破萬，你的直接搜會不會是 n^2 估算 12/12 20:57
→ s89162504: 所以目前討論有兩個改善的方向了 12/12 21:22
→ s89162504: 1 從好一點的點開始 2 改善算上界的方法 12/12 21:23
→ Morris1028: 首先，若全選為最佳解，這樣的總時間為 N^2 12/12 21:24
→ Morris1028: 搜尋空間太大，不應該牽涉到 priority queue 12/12 21:25
→ Morris1028: 直接使用一般的 DFS 搜尋，比較不會讓空間拖累時間 12/12 21:26
→ s89162504: 優先擴展上界較高的點不是比較好嗎？ 12/12 22:44
→ Morris1028: 估算總比預期來得好，意味著找到合法解後，仍有更多 12/13 07:56
→ Morris1028: 的狀態有待搜索，在這種情況空間需求將不切實際 12/13 07:56
→ c910335: 單純好奇「容量又超大」具體是多少？ 12/15 06:48
→ s89162504: 感謝各位 看起來是dfs就行了 12/23 20:10
→ s89162504: best first search 狀態太大時 每次都logn反而變瓶頸 12/23 20:11
推 kyrie77: 輝哥的課嗎XD 02/28 21:07