背包问题 V3（ $01$ 分数规划入门题）-526互联

$\text{description}$
$\text{sol}$
$\text{CODE}$
$\text{Else}$

$\text{description}$

$n$ 个物品的体积为 $w_1,w_2,\cdots,w_n$（$w_i$ 为整数），与之相对应的价值为 $p_1,p_2,\cdots,p_n$（$p_i$ 为整数），从中选出 $k$ 件物品（$k\le n$），使得单位体积的价值最大。

$\text{sol}$

对于题目中的单位体积的价值可以理解为：

\[\max\left\{\frac{\sum_{i=1}^{k}p_i}{\sum_{i=1}^{k}w_i}\right\} \]

其中 $p_i$ 的选取同时会影响到分子和分母的大小，从而影响最终答案，因此无法进行贪心选择。

通过 $01$ 分数规划解决问题，将原本的问题进行转换。

首先令答案为 $x$，那么有 $x=\left(\sum_{i=1}^{k}p_i\right){/}\left(\sum_{i=1}^{k}w_i\right)$。

将其修改得到其变式为

\[\sum_{i=1}^{k}p_i-x\sum_{i=1}^{k}w_i=0 \]

那么就是说这个答案 $x$ 是一定存在一个方案使得上述式子为 $0$。

由此，假如一个 $x'$ 使得上述公式的最大值大于 $0$ 的话，就表示还有更优的答案 $x$，相反同理。

那么就可以考虑二分答案，将每个物品的权值看作 $p_i-x\times w_i$。

这时候我们只需要选择 $k$ 个数，判断其最大值是否大于 $0$ 即可，此时可以选择贪心求解。

$\text{CODE}$

//
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const double eps=1e-5;
double l,r,d[100100],tmp;
int a[100100],b[100100],tmpk[100100];
int tmpp,tmpq,n,k,fq,fp,fk;
int gcd(int a,int b) {
    while(b^=a^=b^=a%=b);
    return a;
}
bool check(double x) {
    tmp=0.00; tmpp=tmpq=0;
    for(int i=1;i<=n;i++) {
        d[i]=1.00*a[i]-1.00*b[i]*x;
        tmpk[i]=i;
    }
    sort(tmpk+1,tmpk+1+n,[](int x,int y){
        return d[x]>d[y];
    });
    for(int i=1;i<=k;i++) {
        tmp+=d[tmpk[i]];
        tmpq+=a[tmpk[i]];
        tmpp+=b[tmpk[i]];
    }
    return tmp>=eps;
}
int main() {
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++) {
        scanf("%d%d",&b[i],&a[i]);
    }
    l=0.00; r=100000.00;
    while(r-l>eps) {
        double mid=(l+r)/2.00;
        if(check(mid)) {
            l=mid;
            fq=tmpq; fp=tmpp;
        }
        else r=mid;
    }
    fk=gcd(fq,fp);
    printf("%d/%d",fq/fk,fp/fk);
    return 0;
}