01分数规划

01分数规划

这是一类常见的问题，通常需要求解的是一个分数表达式的极大值，例如

$$ \frac{\sum_i^j w}{\sum_i^j t} $$

可以采取二分的方式进行约算，设 $x$ 满足

$$ \frac{\sum_i^j w}{\sum_i^j t}\ge x $$

不等式转化为

$$ \sum_i^j w-x*\sum_i^j t\ge 0 $$

后续采取贪心或者动态规划的方式，确定满足题意的最大的 $x$

贪心例：

给定 $n,k$ 数组 $a,b$ 都含有 $n$ 个元素，满足 $a_i\le b_i$ ，可以不选 $k$ 对元素，求满足题意的下列表达式的最大值

$$ ans=max\left[ \frac{\sum a}{\sum b} \right] $$

for (int i=1;i<=n;i++) cin>>a[i];
for (int i=1;i<=n;i++) cin>>b[i];
double l=L,r=R;//根据条件得
while (r-l>0.0001){//精度
    double mid=(l+r)/2;
    if (judge(mid))
        l=mid;
    else 
        r=mid;
}

整理出表达式为

$$ \sum a-ans*\sum b \ge 0 $$

二分答案 $ans$ ，judge 函数内判断是否满足不等式，记 $c_i=a_i-x*b_i$

bool judge(double x){
    double c[1010],sum=0;
    for (int i=1;i<=n;i++) c[i]=a[i]-x*b[i];//计算分项
    sort(c+1,c+1+n);//从小到大排序
    for (int i=k+1;i<=n;i++) sum+=c[i];//贪心选取
    return sum>=0; 
}

感性考虑这样一个问题，从一个从大到小排序的数列中选取 $x$ 个元素使得它们的平均值最大，显然，一定是选前 $x$ 个元素，且 $x $ 越小，它们的平均值越大

所以对这道题而言，我们选取的 $c$ 中的元素越少越好，最多能不选 $k$ 个，那么从大到小选 $n-k$ 个元素一定最优

动态规划例：

给定数组 $a,b$ 都含有 $n$ 个元素，以及限制 $W$ ，选中的 $a_i,b_i$ 中 $\sum b$ 必须满足大于 $W$ 的限制，求

$$ ans=max\left[ \frac{\sum a}{\sum b} \right] $$

double l=L,r=R;
while (r-l>0.00001){
    double mid=(l+r)/2;
    if (judge(mid))
        l=mid;
    else 
        r=mid;
}

二分的操作前面已经说明，变化在于 judge 函数的实现

bool judge(double x){
    for (int j=1;j<=W;j++)
        dp[j]=-1e9;
    for (int i=1;i<=n;i++){
        for (int j=W;j>=0;j--){
            int k=min(j+w[i],W);
            dp[k]=max(dp[k],dp[j]+t[i]-x*w[i]);
        }
    }
    if (dp[W]>=0) return 1;
    else return 0;
}

与 01背包问题类似，经过公式变形后，每件物品的重量为 $b_i$ ，价值为 $a_i-x*b_i$，背包的总容量为 $W$

选 $k$ 件物品的重量要么小于 $W$ 要么大于等于 $W$ ，所以就可以将大于等于 $W$ 的状态统一到 $W$ 上来规划，节约时间

int k=min(j+w[i],W);