约束条件下最优化问题

Published: by Creative Commons Licence

  • Tags:

单调函数求和问题

题目1:给定$m$个线性函数$f_1,\ldots,f_m$,其中$f_i(x)=a_ix+b_i$,现在我们希望为$m$个非负整数未知变量$x_1,\ldots,x_m$赋值,且要求满足$\max_{i=1}^mx_i=n$,在满足约束条件下,要求$\sum_{i=1}^nf_i(x_i)$尽可能大。

我们可以这样来理解这个问题,首先我们有$m$个可投资对象和$n$个资源,且已经获利$\sum_{i=1}^mb_i$,接下来如果我们为第$i$个可投资对象每投入一单位资源,那么就能获利$a_i$,问最大获利多少。

这个自然是将所有资源都砸在$a_i$最大的可投资对象上了。

题目2:给定$m$个函数$f_1,\ldots,f_m$,且每个函数的成像都构成一个上凸包,现在我们要求为$m$个非负整数未知变量$x_1,\ldots,x_m$赋值,且要求满足$\sum_{i=1}^mx_i=n$,在满足约束条件下,要求$\sum_{i=1}^nf_i(x_i)$尽可能大。其中$1\leq m,n\leq 10^5$

利用题目1的方式,我们来试图重新解读问题。首先我们有$m$个可投资对象和$n$个资源,且已经获利$\sum_{i=1}^mf_i(0)$,接下来如果我们为第$i$个可投资对象每投入一单位资源,那么就能获利$f_i(x+1)-f_i(x)$($x$是已经向第$i$个可投资对象投入的资源总量),问最大获利多少。

我们会发现由于所有的函数都是上凸包,因此对于任意$i$,$d_i(x+1)=f_i(x+1)-f_i(x)$是非严格递减函数。考虑到$d_i(1)\geq d_i(2)\geq \ldots$,因此在最终结果中,如果选择$d_i(x+1)$那么我们必定也会选择$d_i(x)$,因此我们可以将所有可选的收益一开始就全部展开${d_i(x)}$,现在我们要做的就是从$d_i(x)$中选择正好$n$个元素,且元素之和最大。这个步骤自然我们会选择使用贪心算法来完成。

现在回到问题,如果我们把所有方案都展开,那么可能会有$nm$个选择,这样太多了,但是由于我们在取得$d_i(x)$之前是不会考虑$d_i(x+1)$的,因此我们可以对每个$i$,仅考虑$x$最小且未被选择的$d_i(x)$。实际操作中,我们只需要维护一个大小为$m$的大根堆即可,当我们将$d_i(x)$弹出的同时,将$d_i(x+1)$加回即可,总的时间复杂度为$O(n\log_2m)$。

提供一道SGU的问题

题目3:给定$m$个函数$f_1,\ldots,f_m$,且每个函数的成像都构成一个上凸包,现在我们要求为$m$个非负整数未知变量$x_1,\ldots,x_m$赋值,且要求满足$\sum_{i=1}^mx_i=n$,在满足约束条件下,要求$\sum_{i=1}^nf_i(x_i)$尽可能大。其中$1\leq m\leq 10^5$,$1\leq n\leq 10^{18}$

这个问题是今天比赛的一道题目学到的。由于是上凸包,因此我们可以用三分算法为每个函数找到其极值点(在非负整数定义域下),记$f_i$的极值点在$p_i$处取到。

分两种情况讨论,如果$n\leq \sum_{i=1}^m p_i$,那么我们可以断定一定有$x_i\leq p_i$,否则对应的就有$x_i\geq p_i$。

如果是$n\leq \sum_{i=1}^m p_i$的情况。记$d_i(x)=f_i(x)-f_i(x-1)$称为函数$f_i$在点$x$处的增量。很显然最优解中,采用的最小增量一定是最大的,我们可以通过二分法找到这个最小增量,这里的时间复杂度为$O(n(\log_2M)^2)$,其中$M$是数据范围。找到最小增量$\delta$后,我们将$x_i$设置为$f_i$增量大于等于$\delta$的整数点数目(不包括0)。那么此时可能会有$\sum_{i=1}^mx_i>n$的情况出现,我们可以保证所有函数增量大于$\delta$的整数点都会被保留(否则为什么要使用增量为$\delta$的点呢?),而增量为$\delta$的点可以删除一部分,来满足$\sum_{i=1}^mx_i>n$,这一部分的时间复杂度为$O(m)$。

对于$n\geq \sum_{i=1}^m p_i$的情况,与上面的方法类似。

最后总的时间复杂度为$O(m(\log_2M)^2)$。

提供一道题目