约束条件下最优化问题

Published: March 30, 2020 by Daltao

• Categories:
• algorithm 101

• Tags:

• 未知数区间约束问题
• 负重问题
• 独立集问题

未知数区间约束问题

题目1：给定$n$个非负未知数$x_1,\ldots,x_n$，以及$m$个条件。第$i$个条件选择一个区间$[l_i,r_i]$以及一个非负数$c_i$，并要求$\sum_{j=l_i}^{r_i}x_i\leq c_i$。在上述约束条件下，我们希望最大化$\sum_{i=1}^nx_i$，如果结果是无穷则输出$-1$。其中$1\leq n,m\leq 10^6$

这个问题可以这样来解决。首先我们可以发现在最优情况下$x_1$一定会取到最大，如果$x_1$未取到最大，则一种情况是$x_2,\ldots,x_n$都是$0$，这时候我们可以让$x_1$增加$1$，这与当前是最优情况相悖。第二种情况是存在一个最小的下标$j$，满足$1\lt j$且$x_j>0$，这时候我们让$x_j$减少$1$，同时让$x_1$增加$1$，重复这个过程直到$x_1$达到最大为止，可以发现这个过程不会导致任意约束条件被破坏。

因此具体的做法按照下标从小到大处理$x_i$，同时维护一个平衡树，平衡树中按照约束$c$排序，存储所有覆盖了$x_i$的约束。之后我们选择最小的约束$y$，并将$x_i$设置为$y$，并将平衡树中所有约束全部减少$y$。

至于无穷，如果我们发现某个未知数没有被约束，则结果为无穷。

这个做法的时间复杂度为$O((n+m)\log_2m)$。

题目2：给定$n$个非负未知数$x_1,\ldots,x_n$，以及$m$个条件。第$i$个条件选择一个区间$[l_i,r_i]$以及一个非负数$c_i$，并要求$\sum_{j=l_i}^{r_i}x_i\geq c_i$。在上述约束条件下，我们希望最小化$\sum_{i=1}^nx_i$。其中$1\leq n,m\leq 10^6$

类似问题1，这个问题也可以贪心解决。首先我们可以发现在最优情况下$x_1$一定会取到最小，如果$x_1$未取到最小，这时候我们让$x_2$增加$1$，同时让$x_1$减少$1$，重复这个过程直到$x_1$达到最小为止，可以发现这个过程不会导致任意约束条件被破坏。

这道题目的做法，就是遍历下标，当我们遍历到$i$的时候，找到所有右边界恰好为$i$的约束，将$x_i$设置为最大的约束值。这个过程可以通过维护前缀和来优化，总的时间复杂度为$O(n+m)$。

题目3：给定$2n$个非负未知数$x_1,\ldots,x_{2n}$，以及$2n$个条件。第$i$个条件要求$\sum_{j=0}^n x_{i+j\pmod{2n}}\leq A_i$。在上述约束条件下，我们希望最小化$\sum_{i=1}^{2n}x_i$。其中$1\leq n\leq 10^5$，$0\leq A_i\leq 10^9$。

提供一道题目。

记$X=\sum_{i=1}^{2n}x_i$，很显然如果存在一种方案的总和为$X$，那么一定存在一种方案的总和为$X+1$。因此我们可以对$X$进行二分。

现在求最小值问题，变成了决策问题，给定一个$X$，判断是否存在一种赋值方案满足条件。

记$0=s_0\leq s_1\leq \ldots \leq s_{2n}=X$，其中$s_i$表示$x_1+\ldots+x_i$。

这时候我们考虑每个条件的意义

• 若$i\leq n$，则对应$s_{n+i-1}-s_{i-1}\leq A_i$
• 若$i>n$，则对应$X-A_i\leq s_{i-1}-s_{i-1-n}$

换言之，对于$0\leq i<n$，都存在这样的约束：$L_i\leq s_{i+n}-s_i\leq R_i$。

我们令$s_n=Y$。我们希望找到一组$s_1\leq \ldots\leq s_{n-1}\leq s_{n+1}\leq \ldots\leq s_{2n-1}$，满足$s_{n-1}\leq Y$以及$s_{2n-1}\leq X$。

我们可以用一个贪心算法来找到最小的$s_{n-1}$和$s_{2n-1}$。具体就是让$i$从$1$遍历到$n-1$。先把$s_i$赋值为$s_{i-1}$，$s_{i+n}$赋值为$s_{i+n-1}$，如果不满足条件，有两种可能：

• $s_{i+n}-s_{i}<L_i$，这时候令$s_{i+n}=s_{i}+L_i$
• $s_{i+n}-s_{i}>R_i$，这时候令$s_i=s_{i+n}-R_i$。

现在令$f_1(a,b)$以及$f_2(a,b)$分别表示当$s_0=a$，且$s_n=b$的时候，通过上面贪心算法得到的最小的$s_{n-1}$和$s_{2n-1}$。

很显然如果$a\leq a'$且$b\leq b'$，那么一定有$f_2(a,b)\leq f_2(a',b')$，因此为了让$f_2(a,b)\leq X$，我们的$Y$不能超过某个上限$H$。

同理我们令$b=0$，$a=-Y$，这时候可以发现，随着$Y$的减小，$f_1(a,b)$会不断增大，因此$Y$不能太小，否则会导致$f_1(a,b)\leq Y$条件被破坏。因此$Y$不能小于某个下限$L$。

我们只需要检查$L\leq H$是否成立即可。查找$L$和$H$都可以通过二分实现。

总的时间复杂度为$O(n(\log_2 M)^2)$，其中$M=O(\max_{i=1}^{2n}A_i)$。

题目4：给定$n$个非负未知数$x_1,\ldots,x_n$，以及$n$个系数$a_1,\ldots,a_n$，以及$m$个条件。第$i$个条件选择一个区间$[l_i,r_i]$以及一个非负数$c_i$，并要求$\sum_{j=l_i}^{r_i}x_i\leq c_i$。在上述约束条件下，我们希望最大化$\sum_{i=1}^na_ix_i$，其中$1\leq n,m\leq 10^4$。

这个题目非常有意思。首先很显然能想到线性规划

$$\begin{align} \max & \sum_{i=1}^na_ix_i\nonumber\\ & \forall i, \sum_{i=l_j}^{r_j}x_i\leq c_i\nonumber\\ & \forall i, x_i\geq 0\nonumber \end{align}$$

但是数据量过大，如果直接用单纯形法，存储系数矩阵所需的空间就达到$O(nm)$级别。

这里顺带一提，由于线性规划有整数解当且仅当系数矩阵是全单模矩阵，恰巧这个矩阵就是全单模的。实际上系数每一行只有0和1，并且所有1都是连续出现的，考虑将其转换为上三角矩阵，可以发现最终得到的矩阵的对角线元素将都是1，因此行列式值只可能是1和-1。

转换成对偶形式

$$\begin{align} \min & \sum_{i=1}^mc_iy_i\nonumber\\ & \forall i, \sum_{\forall j,l_j\leq i\leq r_j}y_j\geq a_i\nonumber\\ & \forall i, y_i\geq 0\nonumber \end{align}$$

对偶问题可以用另一种方式来解释：为持续$n$天的项目招募工人，有$m$类工人，第$i$类工人可以从$l_i$工作到$r_i$，每个工人的费用为$c_i$，且第$j$天的工作至少需要$a_j$个工人。

提供一道题目。

这个问题并不太好解决。我们可以进一步解释这个问题：为持续$n$天的项目招募工人，和INF个免费的不带工具的工人。有$m$类工具套餐，第$i$类工具可以从$l_i$使用到$r_i$，每个工具的费用为$c_i$。目前每天都需要INF个工人带同样数量的工具参加劳作，但是第$j$天只能免费提供$\mathrm{INF}-a_j$个工具。现在问要完成项目至少需要多少费用。

这个问题和刚刚提过的问题是等价的，即第$j$天需要至少提供$a_j$个工具。

而新的问题可以通过网络流来解决，源点向第一天建立一条容量为INF费用为$0$的边，第$j$天向次日（第$n$日向汇点）连容量为$\mathrm{INF}-a_j$费用为$0$的边，而工具$i$则对应从第$l_i$日向$r_i+1$日连的容量为INF费用为$c_i$的边。

这个问题可以通过费用流来计算，具体的时间复杂度不知。

还有一种神奇的做法是通过带上下界费用流来解决。具体就是对于第$j$类工人，我们直接从$r_j+1$向$l_j$连一条容量无穷，费用为$c_j$的边，这条边的容量表示具体雇佣多少第$j$类工人。同时第$i$天向第$i+1$天连一条容量为无穷且下界为$a_j$，费用为0的边。

负重问题

题目1：给定$n$只骆驼，$m$条桥，骆驼需要经过这些桥。其中第$i$只骆驼的重量为$w_i$，第$i$个桥的长度为$l_i$，负重为$v_i$。你可以任意调整骆驼的先后顺序，并且为两只相邻骆驼赋予一个距离。现在希望骆驼队伍能顺利通过所有桥的前提下，最小化队伍头部骆驼和尾部骆驼的距离。如果有若干只骆驼之间最大距离小于$l_i$，且它们的总重量超过$v_i$，则它们不能通过桥$i$。其中$1\leq 8\leq n, 1\leq m\leq 10^5, 1\leq w_i,l_i,v_i\leq 10^9$。

原题

一开始想的是贪心让相邻骆驼距离尽可能接近，利用二分，对于每个排列的时间复杂度为$O(nm\log_210^9)$，但是可以发现实际上我们可以把二分去掉，时间复杂度为$O(nm)$，但是加上排列后时间复杂度为$O(n!nm)$，这个显然太慢了。

我们可以发现对于排列$1,2,\ldots,n$，如果某个距离分配无法通过，则必定存在一个区间$[l,r]$，以及某条桥$i$，区间中的骆驼的总距离小于$l_i$，但是总重量大于$v_i$。因此如果区间都满足桥的约束，则就能顺利通过所有桥。

事实上虽然$m$很大，但是可以发现每个区间$[l,r]$仅存在一个最大的约束条件，而如果通过预处理$m$条桥（桥的负重越大，长度也越大），我们这里可以$O(\log_2m)$得到具体的约束条件。这部分实际上是未知数区间约束问题的第二题，可以在$O(n^2\log_2m)$时间复杂度内解决。

总的时间复杂度为$O(n!n^2\log_2m)$。

独立集问题

题目1：给定$n$个点，其中第$i$个点的位置为$(x_i,y_i)$，它的权重为$w_i$，要求选择一组点，要求这些点都不同行，也不同列，问最大权重之和为多少。

最简单就是进行位压DP，时间复杂度为$O(n2^n)$。这里可以使用meet in middle技巧，可以优化到$O(n2^{\frac{n}{2}})$。如果$n$很小还是不错的。

还可以用最大权拟阵交算法解决这个问题，时间复杂度大致为$O(n^4)$。具体的思路：将$x$当成一种颜色，我们现在定义独立集为不同颜色的元素组成的集合，可以发现这一定义满足拟阵的要求。对于$y$同样处理。满足条件的选择一定同时是两个拟阵中的独立集，于是问题就变成了最大权拟阵交。

还可以用最大权二分图匹配解决这个问题。对应到二维点，可以发现每一行最多取一个元素，每一列最多可以取一个元素。建立一个二分图，一侧顶点代表可能的横坐标，一侧顶点代表可能的纵坐标，对于球$i$，可以对应的加入一条边$(x_i,y_i)$，其权重为球的$w_i$。可以发现满足条件的一种选择方案与二分图的匹配是一一对应的，因此现在的问题变成了求二分图的最大权匹配。这个用费用流跑的话，可以做到$O(n^2\log_2n)$。

题目2：给定$n$个点，对于$i,j$，如果有$|i-j|=a$或$|i-j|=b$，则在两个顶点之间连一条边，否则就不连边。要求计算最大独立集的大小。其中$1\leq n\leq 10^{18}$，$1\leq a,b\leq 22=M$。

一道题目。

这道题目实际上没有太大价值，但是证明用到的技术很不错。

考虑$p=a+b$，记$r=n\pmod p$。考虑最优解的二进制表示形式，我们把它划分为长度为$r$和$p-r$交替的序列$A_1B_1A_2B_2\ldots A_{k-1}B_{k-1}A_{k}$。之后我们不妨设$A_iB_i$是$1$出现总数最大的连续两个元素（还有可能是$B_iA_{i+1}$，证明方法类似）。之后我们可以很安全的将$A_1B_1,A_2B_2,\ldots,A_{i-1}B_{i-1}$替换为多个$A_iB_i$，并将$B_{i+1}A_{i+2},B_{i+2}A_{i+3},\ldots,B_{k}A_{k+1}$替换为多个$B_iA_i$。此时我们的结果是不会变差的，而且由于$A_{i+1}$中的$1$的数目不超过$A_i$中$1$的数目，因此我们同时将$A_{i+1}$替换为$A_i$。此时我们可以发现得到了一个不逊色最优解的答案$A_iB_iA_iB_i\ldots A_iB_iA_i$。

上面的部分证明一定存在一个最优解，其周期为$p$。接下来我们只需要枚举所有可能的前$p$个选择。这里我们可以直接用meet in middle来做，时间复杂度为$O(M2^M)$，当然更好的方法是发现我们只需要决定前$b$个元素，后$a$个元素可以直接贪心选择（这里假设$b\geq a$），时间复杂度是相同的，也是$O(M2^M)$。