背包问题V3 | 分数规划

题解

---

题目描述

N个物品的体积为W1，W2......Wn（Wi为整数），与之相对应的价值为P1,P2......Pn（Pi为整数），从中选出K件物品（K <= N)，使得单位体积的价值最大。

Input
第1行：包括2个数N, K(1 <= K <= N <= 50000)
第2 - N + 1行：每行2个数Wi, Pi（1 <= Wi, Pi <= 50000)

Output
输出单位体积的价值（用约分后的分数表示）。

---

题解

分数规划！

设$x[i]$是布尔类型，$x[i] == 1$表示$i$号物品被选，反之表示不选。

设 $M$ 为单位体积的价值：

$$M = \frac{\sum_{i = 1}^{n}a[i]*x[i]}{\sum_{i = 1}^{n}b[i]*x[i]}$$

我们要求 $M$ 的极值。

我们二分答案 $A$，对于每个$A$，定义一个函数：

$$F(A) = \sum_{i = 1}^{n}a[i]*x[i] - A * \sum_{i = 1}^{n}b[i]*x[i]$$

化简一下：

$$F(A) = \sum_{i = 1}^{n} (a[i] - A * b[i]) * x[i]$$

为了方便起见，设：

$$d[i] = a[i] - A*b[i]$$

则：

$$F(A) = \sum_{i = 1}^{n} d[i] * x[i]$$

接下来考虑$F(A)$与0的关系。根据$F(A) = \sum_{i = 1}^{n}a[i]*x[i] - A * \sum_{i = 1}^{n}b[i]*x[i]$，可以得到：

1. $F(A) > 0 \Leftrightarrow \frac{\sum_{i = 1}^{n}a[i]*x[i]}{\sum_{i = 1}^{n}b[i]*x[i]} > A$，则至少有一组解$x$得到的答案比A优，则A猜小了，应当增加。
2. $F(A) < 0 \Leftrightarrow \frac{\sum_{i = 1}^{n}a[i]*x[i]}{\sum_{i = 1}^{n}b[i]*x[i]} < A$，则不存在任何一组解和A一样优或比A优，则A猜大了，应当减小。

那么我们用$F(A) > 0$来做判断，进行二分即可。

一个注意事项：$F(A)$中的解x，是能使$F(A)$最大的解，则应当按照d[i]将每个物品由大到小排序，选择前k个即可。

最后题目要求输出分数怎么办呢？

还是按照“注意事项”里的，把每个物品按照d[i]排序，选择前k个即可。

---

代码

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iostream>
using namespace std;
const int N = 50005;
int n, k, a[N], b[N], id[N], up, down;
double d[N];
bool f(double l){
    double ret = 0;
    for(int i = 1; i <= n; i++)
        d[i] = a[i] - l*b[i];
    sort(d + 1, d + n + 1);
    for(int i = n; i > n - k; i--)
        ret += d[i];
    return ret >= 0;
}
bool cmp(int x, int y){
    return d[x] > d[y];
}
int gcd(int x, int y){
    return y ? gcd(y, x % y) : x;
}
int main(){
    scanf("%d%d", &n, &k);
    for(int i = 1; i <= n; i++)
        scanf("%d%d", &b[i], &a[i]);
    double l = 0.0, r = 50000.0;
    for(int I = 1; I < 100; I++){
        double mid = (l + r) / 2;
        if(f(mid)) l = mid;
        else r = mid;
    }
    for(int i = 1; i <= n; i++)
        d[i] = a[i] - l*b[i];
    for(int i = 1; i <= n; i++)
        id[i] = i;
    sort(id + 1, id + n + 1, cmp);
    for(int i = 1; i <= k; i++)
        up += a[id[i]], down += b[id[i]];
    int g = gcd(up, down);
    up /= g, down /= g;
    printf("%d/%d\n", up, down);
    return 0;
}