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