wyh的物品_牛客博客

题目描述

wyh学长现在手里有n个物品，这n个物品的重量和价值都告诉你，然后现在让你从中选取k个，问你在所有可能选取的方案中，最大的单位价值为多少（单位价值为选取的k个物品的总价值和总重量的比值）

输入描述:

输入第一行一个整数T(1<=T<=10)
接下来有T组测试数据，对于每组测试数据，第一行输入两个数n和k(1<=k<=n<=100000)
接下来有n行，每行两个是a和b，代表这个物品的重量和价值

输出描述:

对于每组测试数据，输出对应答案，结果保留两位小数

0/1 分数规划

本题可以抽象成给定 $n$ 对整数 $ai$ 和 $bi$ ，从中选出若干对，使选出的数对的 $a$ 之和
与 $b$ 之和的商最大。

不妨猜测一个值 $L$ ，然后考虑这样一个问题，是否存在一种方案使得 $(\Sigma_{i=1}^nai-L*\Sigma_{i=1}^nbi)\geq 0$ 成立。

如果存在这样的方案使得 $(\Sigma_{i=1}^nai-L*\Sigma_{i=1}^nbi)\geq 0$ 成立，那么变形得进一步可知： $\frac{\Sigma_{i=1}^nai}{\Sigma_{i=1}^nbi}\geq L$ 成立。也就是说， $L$ 比我们求的最大值要小。

如果对于任意一种情况，都有 $(\Sigma_{i=1}^nai-L*\Sigma_{i=1}^nbi)< 0$ 成立，那么变形之后可以得到 $\frac{\Sigma_{i=1}^nai}{\Sigma_{i=1}^nbi}< L$ 成立。也就是说， $L$ 比我们求的最大值要大。

这与“二分答案”的情形非常相似,即本题的答案满足单调性。虽然最终的答案是未知的，但是如果我
一个值 $L$ ，就能通过判定是否存在一组解满足 $(\Sigma_{i=1}^nai-L*\Sigma_{i=1}^nbi)\geq 0$ 来确定 $L$ 应该变得更大还是更小。也就是说，解的存在具有单调性。

如何判定“是否存在一组解满足 $(\Sigma_{i=1}^nai-L*\Sigma_{i=1}^nbi)\geq 0$ 呢？显然，我们只需要判定这个式子的最大值是否为非负的。这个判定问题显然比原问题要简单得多，因为 $ai-L*bi$ ；可以直接求出。这就等价于从n个数里选出若干个，使它们的和最大。

综上所述，我们可以二分答案来求解本题。

完整代码

#include<bits/stdc++.h>
using namespace std;
pair<double,double> a[100500];
int n,k;
double c[100500];
bool check(double x){
    for(int i=1;i<=n;++i){
        c[i]=a[i].second-x*a[i].first;
    }
    sort(c+1,c+1+n);
    double sum=0;
    for(int i=n;i>n-k;--i){
        sum+=c[i];
    }
    //cout<<x<<" "<<sum<<endl;
    return sum>=0;
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&k);
        for(int i=1;i<=n;++i)scanf("%lf%lf",&a[i].first,&a[i].second);
        double l=0,r=1e9;
        double ans;
        for(int cnt=0;cnt<100;++cnt){
            double mid=(l+r)/2;
            if(check(mid))ans=mid,l=mid;
            else r=mid;
        }
        printf("%.2f\n",ans);
    }
}