欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

01分数规划

程序员文章站 2022-05-27 21:55:08
问题 $01$分数规划是用来解决这样一类问题 >有$n$个物品,每个物品都有一个属性$p$和$w$。要从中选出$K$个物品使得$\frac{\sum\limits_{i=1}^Kp_i}{\sum\limits_{i=1}^Kw_i}$最大,输出最大值。要求是个分数 ......

问题

\(01\)分数规划是用来解决这样一类问题

\(n\)个物品,每个物品都有一个属性\(p\)\(w\)。要从中选出\(k\)个物品使得\(\frac{\sum\limits_{i=1}^kp_i}{\sum\limits_{i=1}^kw_i}\)最大,输出最大值。要求是个分数

思想

首先二分一个答案\(x\)
然后将上面的问题转化为要选\(k\)个物品使得\[\frac{\sum\limits_{i=1}^kp_i}{\sum\limits_{i=1}^kw_i} \geq x\]
\[\sum\limits_{i=1}^kp_i-\sum\limits_{i=1}^kw_i\times x \ge 0\]
\[\sum\limits_{i=1}^k{p_i-w_i \times x} \ge 0\]
所以对于每个物品,按照上面这个式子排个序。看最大的k个是否满足条件即可。如果满足条件就统计出答案。

例题

51nod 1257

代码

/*
* @author: wxyww
* @date:   2019-02-09 08:30:09
* @last modified time: 2019-02-09 09:00:36
*/
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<bitset>
using namespace std;
typedef long long ll;
const int n = 50000 + 10;
const double eps = 1e-9;
ll read() {
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9') {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
struct node {
    int w,p;
    double x;
}a[n];
bool tmp(node x,node y) {
    return x.x > y.x;
}
int n,k;
int check(double w,int &x,int &y) {
    for(int i = 1;i <= n;++i)
        a[i].x = double(a[i].w) - double(a[i].p * w);
    sort(a + 1,a + n + 1,tmp);
    double ans = 0;
    for(int i = 1;i <= k;++i) ans += a[i].x;
    if(ans >= 0) {
        x = 0,y = 0;
        for(int i = 1;i <= k;++i) {
            x += a[i].w;
            y += a[i].p;
        }
        int g = __gcd(x,y);
        x /= g; y /= g;
        return 1;
    }
    return 0;
}
int main() {
    n = read();
    k = read();
    double r = 0;
    for(int i = 1;i <= n;++i) a[i].p = read(),a[i].w = read(),r = max(r,(double)a[i].w);
    double l = 0;
    int x,y;
    while(r - l > eps) {
        double mid = (l + r) / 2;
        if(check(mid,x,y)) l = mid;
        else r = mid;
    }
    printf("%d/%d\n",x,y);
    return 0;
}