『0/1分数规划二分法』

<更新提示>

<第一次更新>

<正文>

0/1分数规划

模型

0/1分数规划指的是这样一个问题模型：

给定整数$a_1,a_2,...,a_n$和$b_1,b_2,...,b_n$，求一组解$x_1,x_2,...,x_n(\forall\ i\in[1,n],x_i=1,0)$，使得下式最大化：$$\frac{\sum_{i=1}^{na_i*x_i}{\sum_{i=1}}nb_i*x_i}$$

简单地说，就是给定$n$对整数$a_i,b_i$，从中选取若干对，使得选出的$a$之和与$b$之和的比值最大。

二分法

这个问题模型可以使用二分法解决。

不妨二分枚举一个数$L$，然后考虑是否存在一组解，使得$\sum_{i=1}^n(a_i-Lb_i)*x_i\geq 0$。

$1.$ 若存在一组解，使得$\sum_{i=1}^n(a_i-Lb_i)*x_i\geq 0$，则显然有$\sum_{i=1}^na_ix_i-L\sum_{i=1}^nb_ix_i\geq 0$，那么就有$$\exists {x_1,x_2,...,x_n},\frac{\sum_{i=1}^{na_i*x_i}{\sum_{i=1}}nb_i*x_i}\geq L$$

就可以得到最优解一定大于等于$L$。

$2.$ 若对于每一组解，都有$\sum_{i=1}^n(a_i-Lb_i)*x_i< 0$，则同理可知

\[\forall \{x_1,x_2,...,x_n\},\frac{\sum_{i=1}^na_i*x_i}{\sum_{i=1}^nb_i*x_i}< L \]

就可以得到最优解一定不到$L$。

那么我们就可以依次进行二分答案，最后的结果就是$L$。

求解形如$\sum_{i=1}^n(a_i-Lb_i)*x_i$是否非负的问题是简单的，由于$a_i-Lb_i$的值可以直接计算，所以直接取适当的$x_i$，让上式最大化或最小化即可。

Dropping Test

Description

给定你n组ai,bi，让你取出n−k组，使得这n−k组的a之和除以b之和最大.

Input Format

输入包括多组数据.

每组数据第一行包括两个数n和k，意义如题，若n和k为0表示输入结束.

接下来一行n个数，第i个数表示ai.再接下来一行n个数，第i个数表示bi.

Output Format

对于每组输入数据输出一行一个数表示答案，答案保留整数.

Sample Input

Sample Output

83
100

解析

$0/1$分数规划模板题，直接二分答案，然后暴力排序判定即可。

$Code:$

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=1e3+20;
const double eps=1e-7;
int n,k;
double a[N],b[N],val[N],ans;
inline void input(void)
{
    for (int i=1;i<=n;i++)
        scanf("%lf",&a[i]);
    for (int i=1;i<=n;i++)
        scanf("%lf",&b[i]);
}
inline double check(double L)
{
    double res = 0.0;
    for (int i=1;i<=n;i++)
        val[i] = a[i] - L * b[i];
    sort( val+1 , val+n+1 );
    for (int i=n;i>=k+1;i--)
        res += val[i];
    return res;
}
inline void fraction_planning(void)
{
    double l=0.0,r=1e9,mid;
    while ( l + eps < r )
    {
        mid = (l+r) / 2;
        if (check(mid)>=0)l=mid;
        else r=mid;
    }
    ans = mid*100;
}
int main(void)
{
    while ( scanf("%d%d",&n,&k) && (n|k) )
    {
        input();
        fraction_planning();
        printf("%.0lf\n",ans);
    }
    return 0;
}

<后记>

『0/1分数规划 二分法』