01分数规划

据说这玩意叫数学?

学,我学还不行么….


01分数规划是从分数规划中分支出来的一个比较简单的一部分.

之所以叫01分数规划是因为这类问题需要求解一个比例最值问题.

套着分数所以叫分数规划,想想差不多啊

对于一个物品,我们有价值\(val[i]\)和消耗\(cost[i]\)两种,对于这个物品,只有选和不选的操作.

如果选了这个物品,可以理解为有一个对应选不选的数组\(x[i]\),即\(x[i]=1\).

那么一定会有价值和消耗.

我们需要找到价值和/消耗和这个比例最值的情况.


我们列一个可爱的式子

\[R=\frac{\sum_{i=1}^n(val[i]*x[i])}{\sum_{i=1}^n(cost[i]*x[i])}\]

什么?不可爱?来,看我把他变得可爱

对于这个式子可以发现,我们所需要求解的一个比例的最值即为\(R\)的最值.

现在我们构造一个函数\(F(l)\)

\[F(l)=\sum_{i=1}^n(val[i]*x[i])-l*\sum_{i=1}^n(cost[i]*x[i])\]

现在我们可以发现他变得更加不可爱了这个函数是一个关于\(l\)的函数废话

而且我们想让之前的那个\(R\)尽可能大相当于让\(l\)尽可能大

所以.

我们

需要

进一步让这个式子变得可爱.

\[F(l)=\sum_{i=1}^n[(val[i]-cost[i])*x[i]]\]

再可爱一点??

令\(All[i]=val[i]-cost[i]\)

所以我们可以得到这个式子的究极可爱版

\[F(l)=\sum_{i=1}^n(All[i]*x[i])\]

从前面的推导可以发现,我们其实最后在做的事情就是让\(L\)不断增大.

那么从这个究极可爱版的式子可以看出我们可以判断\(All[i]\)是否存在来让前文中说到的\(R\)尽可能大

我们假设存在一种\(x\)的分布方案使得\(F(l)\geq0\),有了大于0的方案了,而且根据函数单调性可以发现,如果\(l\)越大,\(All[i]\)只会越小.所以多数情况是小于0的.

而我们所要求的极限最值,也就是\(R_{max}\)是当这个式子等于0的时候出现的.

如果存在大于0的方案,那么说明一定存在等于0的方案,即一定存在最优解.

所以怎么求这个最优解?


二分!

通过一些玄学的计算算出M

比如通过\(All\)

然后判断\(M\)是否大于0就好了.

记得设一个\(eps\)卡一下精度….

Dinkelbach!

这是一种完全没听过据说不如二分的牛逼算法.

其实,我们前面提到当\(F(l)==0\)时是当前的最优解.

这个是Dinkelbach定理.

当然Dinkelbach就有了算法.

不同于二分.

因为我们最开始要求解的式子是

\[R=\frac{\sum_{i=1}^n(val[i]*x[i])}{\sum_{i=1}^n(cost[i]*x[i])}\]

而且\(x[i]\)要么同时为1,要么同时为0.

就这两种

所以答案可以看成

\[R=\frac{\sum_{i=1}^nval[i]}{\sum_{i=1}^ncost[i]}\]

所以我们既然已经任意指定了一个答案\(ans\)

可以把这个答案带入后面变形的式子,也就是\(All\)

可以算出当\(All\)最小的时候的一组,也就是上面二分的时候的\(M\)

然后通过这个\(M\)重新算出一个\(ans\)

新的\(ans=\frac{val[M]}{cost[M]}\)

继续这样做,一直迭代下去,直到满足精度为止.

我觉得除了最后一句满足精度为止不理解以外其他倒没什么了呢

这个和二分相比..

它比二分好像要更快一些.

但是判断一个解和求出一个解的时间复杂度是不一样的.

而且这个还要把解存下来.

所以各有利弊吧.

各位加油~我水题去了


By:Wahacer

2017.12.21

21:05

01分数规划》有2个想法

发表评论

电子邮件地址不会被公开。 必填项已用*标注