Wqs二分

Published: by Creative Commons Licence

  • Tags:

WQS二分

考虑有$n$个物品,物品$i$的权重为$w_i$。我们需要从中正好选择$k$件物品,要求取出的物品总权重最大。

当然这个大家都知道可以用贪心算法解决。只要取权重最大的$k$件物品即可。但是这里要讲一下动态规划的求法。

我们可以定义$dp(i,j)$表示从前$i$件物品中取出$j$件,可以得到的最大权重。这样就可以得出递推公式:$dp(i,j)=\max(dp(i-1,j-1)+w_i, dp(i-1,j))$。

但是这样的写法是$O(n^2)$的,能不能更加快一些呢。我们会发现如果可以取任意件的时候,我们就可以将动态规划公式优化为$f(i)$,表示从前$i$件物品中最大能取出的权重,那么有$f(i)=\max(f(i-1),f(i-1)+w_i)$。这时候动态规划求法和贪心的速度是一样的。

这里要说一下WQS二分。记录$g(i)$表示从$n$件物品中仅能取$i$件物品时的最大总权,且满足$g(i)-g(i-1)\geq g(i+1)-g(i)$,即$g$的曲线是上凸的,那么我们就可以用一些斜线去切这个上凸包,从而得到凸包上每个顶点的信息。

做法就是我们为选择每个商品时都赋予一定的惩罚$c$(即用来切凸包的直线的斜率),很显然惩罚越大,我们最优解时进行的选择就会越少。因此我们可以二分惩罚,来得到恰好选择$k$次的结果$r$,我们可以将$r$加上$kc$就可以得到真正的结果了。(我们仅需二分斜率而不需要考虑直线在y轴上的截距,因为截距仅相当于在最终解上加上固定的常数,这不会影响不同解之间的比较关系)

这里需要注意的是不一定能正好二分到$k$次,比如所有物品的权重都相同,那么无论惩罚如何选择,要么一件不选,要么都选。但是这时候我们会发现多选带来的收益(在考虑惩罚的情况下)一定是0,因此我们可以不用在乎多选的情况,只要在最终结果仅加上$kc$(最后加上的数与最优解的时候实际选择的商品数无关,比如这里即使选择了$n$件商品,也仅加上$kc$而非$nc$)即可。

还需要注意由于我们很难确定惩罚的精度,因此就很难控制二分的次数。这里有一个简单的方法,就是二分一个固定的次数$T$,比如取$T=60$,显然次数越大,结果的精度也越高。

一道不错的例题

题目1:有$n$只宝可梦,你手头有$a$个普通球,$b$个橡木球,当使用普通球捕获第$i$只宝可梦时概率为$p_i$,用橡木球捕获第$i$只宝可梦的时候概率为$q_i$。你可以对某只宝可梦丢普通球或橡木球,也可以同时使用两个不同种类的球。现在希望规划好所有的球使用的对象,要求让捕获到的宝可梦的数量的期望最大。问最大期望是多少。其中$1\leq a,b \leq n\leq 10^4$。

对于第$i$只精灵,如果仅使用普通球,则捕获的概率为$p_i$,仅使用橡木球,捕获的概率为$q_i$,如果使用两种球,则捕获的概率为$p_i+q_i-p_iq_i$。

一般的思路就是使用动态规划。记$dp(i,j,k)$表示对前$i$只宝可梦,使用$j$个普通球,使用$k$个橡木球,最大的捕获到的宝可梦数量的期望是多少。

上面的递推我们可以在$O(nab)$时间复杂度内求解,太慢了。

有一种非常有趣的做法就是使用费用流。每个宝可梦向普通球连一条容量为$1$,费用为$-p_i$的边,向橡木球连一条容量为$1$,费用为$-q_i$的边。同时从源点向每只宝可梦连一条容量为$1$费用为$0$的边,以及容量为$1$费用为$p_iq_i$的边。于是乎,我们就能通过费用流来求解这个问题,由于边和顶点的数目都是$O(n)$,因此如果我们使用Dijkstra优化的费用流,可以在$O(n^2\log_2n)$的时间复杂度内求解,已经很快了。

上面费用流的做法很不错,但是缺点是如果我们扩展球的种类,那么费用流就无法支持了,它仅能巧妙的支持两种球。

对应的这个问题还有一种用WQS的做法。可以发现上面的动态规划公式约束我们必须使用$a$个普通球和$b$个橡木球。我们可以发现以$a$为横坐标,最终结果是一个上凸包(对应的以$b$为横坐标也是如此)。因此我们可以用WQS去掉$a$的约束。现在问题还有一个$b$的约束,我们同理也可以通过WQS去掉$b$的约束,因此总的时间复杂度为$O(T^2n)$,其中$T$为二分循环的次数,一般选$100$以内即可。

可以发现即使扩展新的球的种类,WQS依旧可以很好的支持,如果有$k$种类型的球,则时间复杂度应该为$O(T^k2^kn)$。

提供一道题目

题目2:给定$n$个元素,其中第$i$元素有两个属性$a_i,b_i$。现在需要从$n$个元素中选择两个不相交集合$A$和$B$,其中$A$的大小正好为$x$,$B$的元素大小正好为$y$。要求$\sum_{i\in A}a_i+\sum_{i\in B}b_i$最大。要求算出最大和。其中$1\leq n\leq 10^6$,$1\leq a_i,b_i\leq 10^9$

提供一道题目

考虑到随着$x$的增大,总和增大的幅度会不断减少,换言之总和是关于$x$的上凸函数。因此我们可以通过套用WQS去掉$x$的限制,对应的代价就是最终的时间复杂度要乘上一个$T$,即二分次数。

当然用同样的技术可以去除$y$的限制,但是这样的时间复杂度会达到$O(T^2n)$,通常$T$取到$30$以上,因此这样是不可行的。

可以发现当$x$去掉后,每次操作的费用为$cost$的时候,问题变成第$i$个元素被选择后可以获利$a_i-cost$,而这个元素实际对结果的贡献为$\max(0,a_i-cost)$。而如果我们选择$i$加入$B$,则表示我们可以额外获利$b_i-\max(0,a_i-cost)$。因此我们可以选择额外获利最多的前$b$个元素即可。这个可以通过k-th element技术线性计算得到。

总的时间复杂度为$O(Tn)$。