定义

$\space\space\space\space\space$ 0/1分数规划模型是指 给定整数 $a_1, a_2, a_3,...., a_n$以及$b_1, b_2, b_3, .....b_n$, 求一组解$x_i(1 \leq i \leq n, x_i = 0或1)$ 使下式最大化
$$ \frac{\sum_{i = 1}^{n}a_i * x_i}{\sum_{i = 1}^{n} b_i * x_i}$$
$\space\space\space\space\space$ 通俗地说 就是给定n对整数$a_i, b_i$ 从中选出若干对，使选出的数对的a之和与b之和的商最大
$\space\space\space\space\space$

思路

$\space\space\space\space\space$ 求解0/1分数规划的通常做法是二分答案
$\space\space\space\space\space$ 即可以在值域[L,R]内二分mid 判断是否存在一组解$x_i$使得$$ \frac{\sum_{i = 1}^{n}a_i * x_i}{\sum_{i = 1}^{n} b_i * x_i} \geq mid$$
$\space\space\space\space\space$ 若是则说明二分值mid比能求得的最大值要小 即我们应该向mid大的方向找 令L = mid
$\space\space\space\space\space$ 否则说明二分值mid比能求得的最大值要大 即我们应该向mid小的方向找 令R = mid

转化

$\space\space\space\space\space$ 我们试着做出如下变化 $$ \frac{\sum_{i = 1}^{n}a_i * x_i}{\sum_{i = 1}^{n} b_i * x_i} \geq mid$$
$$ ( {\sum_{i = 1}^{n}a_i * x_i}) - mid *( {\sum_{i = 1}^{n} b_i * x_i}) \geq 0$$
$$ {\sum_{i = 1}^{n}(a_i - mid * b_i) * x_i} \geq 0$$

$\space\space\space\space\space$然后我们只需要判断进行01的规划 若$a_i - mid * b_i < 0$则令$x_i = 0, 反之x_i 为1$

实例-1 例题 K : Best

题意

$\space\space\space\space\space$ 我们先来看看这样一种分数规划模型 给定整数 $a_1, a_2, a_3,...., a_n$以及对应的$b_1, b_2, b_3, .....b_n$,从中任意选出k对 使下式最大化
$$ \frac{\sum_{j = 1}^{k}a_{i_j}}{\sum_{j = 1}^{k} b_{i_j}}$$

思路

$\space\space\space\space\space$ 求解分数规划的通常做法是二分答案
$\space\space\space\space\space$ 即可以在值域[L,R]内二分mid 判断是否存在一组解$x_i$使得$$ \frac{\sum_{i = 1}^{n}a_i}{\sum_{i = 1}^{n} b_i} \geq mid$$
$\space\space\space\space\space$ 若是则说明二分值mid比能求得的最大值要小 即我们应该向mid大的方向找 令L = mid
$\space\space\space\space\space$ 否则说明二分值mid比能求得的最大值要大 即我们应该向mid小的方向找 令R = mid
$\space\space\space\space\space$ 即最终只需要判断
$$ {\sum_{i = 1}^{n}(a_i - mid * b_i) } \geq 0$$
$\space\space\space\space\space$ 如果该式大于等于0 即返回true 反之 返回false

AC源码

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#define eps 0.000000001
using namespace std;
const int N = 1e5+10 , INF = 1e6+10 ;

int n , k ;

struct node
{
    int v , w , id;
    double op;//op 代表每个点的v - x * w的情况
}f[N];

bool cmp(node a ,node b)//我们对op从大到小排序 ---贪心选k个 
{
    return a.op > b.op;
}

bool check(double x)
{
    double sum = 0;
    for(int i = 0 ; i < n ; i ++ ) f[i].op = f[i].v - x * f[i].w; //记录 v - x * w的数据

    sort(f , f + n , cmp );//排序

    for(int i = 0 ; i < k ; i ++ ) sum += f[i].op; //记录前k个op值 
    return sum >= eps; //如果大于0返回true  反之false
}


int main()
{

    cin >> n >> k ;
    for(int i = 0  ; i < n ; i++)
    {
        scanf("%d %d",&f[i].v , &f[i].w);
        f[i].id = i + 1 ; 
    }

    double l = 0 , r = INF;

    while(r - l  > eps) //二分答案 浮点数板子
    {
        double mid = ( l + r )/2;
        if(check(mid)) l = mid ;
        else r = mid;
    }

    for(int i = 0 ; i < k ; i ++)printf("%d ",f[i].id);
    cout << endl; 
}

例题-2 Dropping tests

解析

$\space\space\space\space\space$本题跟上题没什么区别 只要输入输出改下即可

AC源码

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#define eps 0.000000001
using namespace std;
const int N = 1e5+10 , INF = 1e6+10 ;

int n , k ;

struct node
{
    int v , w;
    double op;//op 代表每个点的v - x * w的情况
}f[N];

bool cmp(node a ,node b)//我们对op从大到小排序 ---贪心选k个 
{
    return a.op > b.op;
}

bool check(double x)
{
    double sum = 0;
    for(int i = 0 ; i < n ; i ++ ) f[i].op = f[i].v - x * f[i].w; //记录 v - x * w的数据

    sort(f , f + n , cmp );//排序

    for(int i = 0 ; i < k ; i ++ ) sum += f[i].op; //记录前k个op值 
    return sum >= eps; //如果大于0返回true  反之false
}


int main()
{

    while(cin >> n >> k, n || k)
    {


        k = n - k;
        for(int i = 0; i < n; i ++) cin >> f[i].v;
        for(int i = 0; i < n; i ++) cin >> f[i].w;


        double l = 0 , r = INF;

        while(r - l  > eps) //二分答案 浮点数板子
        {
            double mid = ( l + r )/2;
            if(check(mid)) l = mid ;
            else r = mid;
        }
        double cnt1 = 0, cnt2 = 0, res = 0; 

        for(int i = 0 ; i < k ; i ++)cnt1 += f[i].v, cnt2 += f[i].w;
        res = (cnt1 / cnt2) * 100;

        printf("%.0lf\n", res);
    }
}

相思例题

Desert King
P3199 [HNOI2009]最小圈
P4377 [USACO18OPEN] Talent Show G
观光奶牛