题意简述：
有$n$个物品和一个容量为$w$的背包 求出背包最多能装多大体积的物品 ($w\leq 2^{31}-1$,$n\leq 45$)
题解：
该题是经典的超大背包问题 对于这样这样$n$很小$v$很大的背包问题我们可以考虑搜索 假如直接枚举的话那么时间复杂度为$O(2^{45})$显然超时 所以我们可以想到用空间来换时间 也就是折半搜索或者中途相遇法 我们首先把前一半的物品枚举出所有可能的和并放在集合$a$中 时间复杂度$O(2^{\frac{n}{2}})$ 大概是$6\cdot10^6$ 之后我们进行一个排序去重 然后再枚举剩下一半 假如剩下一半和为$sum$ 那么我们从之前的$a$集合中找到$\leq w-sum$的最大的值 这里可以二分操作 把这两个一加就是当前最大的填满的 然后取$max$即可得到$ans$ 总体的时间复杂度大概是$O(2^{\frac{n}{2}}log(2^{\frac{n}{2}}))=O(\frac{n}{2}\cdot 2^{\frac{n}{2}})$
好的 思路看上去也就这样 没啥难的 然后我开心的在acwing交了几发 TLE TLE TLE调过以后在tyvj又交了几发TLE 真是太玄学了 记录一下我的调试历程
首先是若干剪枝 这没啥好说的 在枚举集合时候发现已经超过$w$就退出即可 然后在二分的时候假如当前$sum$加上最小的$a$也大于$w$那么退出
之后是优化搜索顺序 比较套路 我们可以直接考虑排序 让最大的前一半排在前面 这样前面的和就比较大 可以使得后面的搜索树深度减少
然后就是在枚举子集和的时候我一开始是for枚举子集 但是它每一次都会有一个for循环求和的过程 所以还是最好就用dfs去枚举子集和 然后后一半检验是最玄学的 我用for循环枚举子集在tyvj就可以过 用dfs却被卡 然后dfs中的二分改成upper_bound反而又过了 按理来说应该会慢啊 我还试着在acwing上用upper_bound开了O2发现还是比手写慢不少 就很迷惑
另外需要注意的是一半的取值 这里假如直接取$\frac{n}{2}$应该是过不了的反正我过不了 据实验最快的取值应该是$\frac{n}{2}+2$ 我这里来胡扯分析一波
首先我们可以看到瓶颈就是两个dfs 排序本身虽然复杂度也同级但其实不会拖累整体 那么我们第一次dfs时间复杂度是$O(2^{\frac{n}{2}})$ 第二次是$O(\frac{n}{2}\cdot 2^{\frac{n}{2}})$ 其实发现第二次会更大一些 那么我们为了均摊复杂度会想让两次的复杂度差不多 我们考虑一下前一半取$k$个 那么时间复杂度分别为$2^k$和$k\cdot2^{n-k}$ 当$k=\frac{n}{2}+2$时两边分别为$4\cdot2^{\frac{n}{2}}$和$\frac{n+4}{8}\cdot2^{\frac{n}{2}}$
因为$n\in[1,45]$ 所以$n$平均是$23$左右 然后带进去发现前面和4很接近 所以当前一半取$\frac{n}{2}+2$时均摊复杂度是最理想的 当然这个证明有些不严谨 不过应该可以感性理解了
AC代码
|
|