作者s89162504 (路人甲)
看板Prob_Solve
标题[问题] 01背包的暴搜有甚麽特别的剪枝吗?
时间Wed Dec 11 19:05:24 2019
01背包是假多项式
背包容量超大时无法DP
只能用branch and bound
一般教科书上提到的剪枝的方法:
把物品依照CP值排序 CP值高的先放进去
用贪心法计算upper bound
upper bound比较大的点优先扩展
想请问各位大大
还有甚麽特别的方法可以加速吗?
小弟在修演算法的课
卡一笔测资1000个物品 容量又超大
感谢
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 223.140.95.72 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1576062326.A.648.html
※ 编辑: s89162504 (223.140.95.72 台湾), 12/11/2019 19:06:38
1F：→ oToToT: 价值也超大吗? 12/11 19:17
2F：→ s89162504: 对啊 12/11 19:22
3F：→ s89162504: 有推荐类似的OJ题目吗? 我查到的都还是一般的branch 12/11 19:23
4F：→ s89162504: and bound 12/11 19:23
5F：推 Morris1028: 在搜寻前, 给予一个好的初始值, 而非在搜寻过程慢慢 12/12 06:43
6F：→ Morris1028: 更新 12/12 06:43
7F：推 Morris1028: 那麽有较好的初始值後, 总是先选与不选就要看测资的 12/12 06:55
8F：→ Morris1028: 状况有明显差异 12/12 06:55
9F：→ s89162504: morris的意思是直接用upper bound很高的可行解下去暴搜 12/12 16:47
10F：→ s89162504: 吗？ 12/12 16:47
11F：→ s89162504: 可是如果最佳解其实在另一边 会不会反而做白工啊？ 12/12 16:48
12F：→ Hsins: 听起来很像是辉哥ㄉ课欸>< 12/12 18:49
13F：→ s89162504: 是喔 补考想把那笔测资过了 12/12 19:45
14F：→ Morris1028: 这一题收录 批改娘 20005 12/12 20:06
15F：→ Morris1028: 最後的测资我没让 bound and branch 的方式通过, 所 12/12 20:08
16F：→ Morris1028: 以拿个 90 分不是问题 12/12 20:08
17F：→ Morris1028: 着重还是在 upper bound 能算多快, 若每次从头跑到尾 12/12 20:25
18F：→ Morris1028: 那一种就太慢了 12/12 20:25
19F：→ s89162504: 所以是 目前枚举到第i项物品 剩余空间w 12/12 20:33
20F：→ s89162504: 要事先建一个(i,w)的表吗? 12/12 20:34
21F：→ s89162504: 会不会太大了XD 12/12 20:37
22F：推 Morris1028: 没看到代码，我不好说可能少哪一块基础 12/12 20:56
23F：→ Morris1028: 但是当 n 破万，你的直接搜会不会是 n^2 估算 12/12 20:57
25F：→ s89162504: 所以目前讨论有两个改善的方向了 12/12 21:22
26F：→ s89162504: 1 从好一点的点开始 2 改善算上界的方法 12/12 21:23
27F：→ Morris1028: 首先，若全选为最佳解，这样的总时间为 N^2 12/12 21:24
28F：→ Morris1028: 搜寻空间太大，不应该牵涉到 priority queue 12/12 21:25
29F：→ Morris1028: 直接使用一般的 DFS 搜寻，比较不会让空间拖累时间 12/12 21:26
30F：→ s89162504: 优先扩展上界较高的点不是比较好吗？ 12/12 22:44
31F：→ Morris1028: 估算总比预期来得好，意味着找到合法解後，仍有更多 12/13 07:56
32F：→ Morris1028: 的状态有待搜索，在这种情况空间需求将不切实际 12/13 07:56
33F：→ c910335: 单纯好奇「容量又超大」具体是多少？ 12/15 06:48
34F：→ s89162504: 感谢各位 看起来是dfs就行了 12/23 20:10
35F：→ s89162504: best first search 状态太大时 每次都logn反而变瓶颈 12/23 20:11
36F：推 kyrie77: 辉哥的课吗XD 02/28 21:07