分数规划学习笔记

Author Avatar
Sakits 4月 11, 2018

简介

  这东西我已经学了五六遍了…每次能保持记忆的时间都不超过一个月,还是写个笔记存一下好了…
  给定两个数组ai,bia_i,b_iaia_i表示收益,bib_i表示代价,每个点都可以选或者不选,选则xi=1x_i=1否则xi=0x_i=0,问题即求下式的最值。

i=1naixii=1nbixi\frac{\sum_{i=1}^n a_ix_i}{\sum_{i=1}^n b_ix_i}

分析

  令

R=i=1naixii=1nbixiR=\frac{\sum_{i=1}^n a_ix_i}{\sum_{i=1}^n b_ix_i}

  则要使RR取得最值。
  令

F(L)=i=1naixiLi=1nbixi=i=1nxi(aiLbi)\begin{aligned} F(L)&=\sum_{i=1}^n a_ix_i-L\sum_{i=1}^n b_ix_i\\ &=\sum_{i=1}^nx_i(a_i-Lb_i) \end{aligned}

  实际上上式的LL就是要求的最值RR
  二分LL,若有一种方案使得:F(L)>0F(L)>0,则有:

i=1naixiLi=1nbixi>0i=1naixii=1nbixi>L\begin{gathered} \sum_{i=1}^n a_ix_i-L\sum_{i=1}^n b_ix_i>0\\ \frac{\sum_{i=1}^n a_ix_i}{\sum_{i=1}^n b_ix_i}>L \end{gathered}

  所以F(L)>0F(L)>0说明有一个更优的答案
  若F(L)<0F(L)<0,代回原式:

L>i=1naixii=1nbixiL>\frac{\sum_{i=1}^n a_ix_i}{\sum_{i=1}^n b_ix_i}

  说明不存在方案使答案达到LL,故F(L)=0F(L)=0时求得最值

基本流程

  二分答案LL,将所有数字改为aiLbia_i-Lb_i,求得符合题目条件的最值,代入F(L)F(L)判断。

例题

  1.1.bzoj3232: 圈地游戏
  2.2.bzoj2285: [Sdoi2011]保密
  3.3.bzoj4898: [Apio2017]商旅