Wqs二分

Published: July 31, 2020 by Daltao

• Categories:
• algorithm 101

• Tags:

• WQS二分

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)$。