P4377 [USACO18OPEN] Talent Show G

[P4377 USACO18OPEN] Talent Show G - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

P4377 [USACO18OPEN] Talent Show G

题目

题目描述

Farmer John 要带着他的 \(n\) 头奶牛，方便起见编号为 \(1\ldots n\)，到农业展览会上去，参加每年的达牛秀！他的第 \(i\) 头奶牛重量为 \(w_i\)，才艺水平为 \(t_i\)，两者都是整数。

在到达时，Farmer John 就被今年达牛秀的新规则吓到了：

（一）参加比赛的一组奶牛必须总重量至少为 \(W\)（这是为了确保是强大的队伍在比赛，而不仅是强大的某头奶牛），并且。

（二）总才艺值与总重量的比值最大的一组获得胜利。

FJ 注意到他的所有奶牛的总重量不小于 \(W\)，所以他能够派出符合规则（一）的队伍。帮助他确定这样的队伍中能够达到的最佳的才艺与重量的比值。

输入格式

第一行是两个整数，分别表示牛的个数 \(n\) 和总重量限制 \(W\)。

第 \(2\) 到 \((n+1)\) 行，每行两个整数，第 \((i + 1)\) 行的整数表示第 \(i\) 头奶牛的重量 \(w_i\) 和才艺水平 \(t_i\)。

输出格式

请求出 Farmer 用一组总重量最少为 \(W\) 的奶牛最大可能达到的总才艺值与总重量的比值。

如果你的答案是 \(A\)，输出 \(1000A\) 向下取整的值，以使得输出是整数（当问题中的数不是一个整数的时候，向下取整操作在向下舍入到整数的时候去除所有小数部分）。

样例 #1

样例输入 #1

样例输出 #1

提示

样例解释

在这个例子中，总体来看最佳的才艺与重量的比值应该是仅用一头才艺值为 \(11\)、重量为 \(10\) 的奶牛，但是由于我们需要至少 \(15\) 单位的重量，最优解最终为使用这头奶牛加上才艺值为 \(21\)、重量为 \(20\) 的奶牛。这样的话才艺与重量的比值为 \(\frac{11+21}{10+20}=\frac{32}{30} = 1.0666\dots\)，乘以1000向下取整之后得到 \(1066\)。

数据规模与约定

对于全部的测试点，保证 \(1 \leq n \leq 250\)，\(1 \leq W \leq 1000\)，\(1 \leq w_i \leq 10^6\)，\(1 \leq t_i \leq 10^3\)。

思路

正解是01分数规划 + 背包

1、分数规划

二分答案

\[\sum \frac{t_i}{w_i} \geq mid \]

即

\[\sum(t_i - mid * w_i) \geq 0 \]

所以

\[p_i = t_i - mid * w_i \]

2、背包

设 dp[i] 表示重量为 \(i\) 时可以取到 \(p\) 最大的值。

大于等于 \(W\) 的都存在 \(dp[W]\) 上，这个就是答案。

那么

\[dp[j + w[i]] = max (dp[j + w[i]] , dp[j] + c[i]) \]

code

#include <bits/stdc++.h>
#define fu(x , y , z) for(int x = y ; x <= z ; x ++)
#define fd(x , y , z) for(int x = y ; x >= z ; x --)
#define LL long long
using namespace std;
const int N = 255 , M = 1005;
const double eps = 1e-6;
const int inf = 1e8 + 5;
int n , W;
double p[N] , dp[M];
LL w[N] , t[N] , st;
double ck () {
    fu (i , 1 , W) dp[i] = -inf;
    fu (i , 1 , n) {
        fd (j , W , 0) {
            if (j + w[i] >= W) dp[W] = max (dp[W] , dp[j] + p[i]);
            else dp[j + w[i]] = max (dp[j + w[i]] , dp[j] + p[i]); 
        }
    }
    return dp[W];
}
double fans () {
    double l = 0 , r = st , mid;
    while (r - l > eps) {
        mid = (l + r) / 2;
        fu (i , 1 , n) p[i] = t[i] - w[i] * mid;
        if (ck () >= eps) l = mid + eps;
        else r = mid;
    }
    return l;
}
int main () {
    scanf ("%d%d" , &n , &W);
    fu (i , 1 , n)
        scanf ("%lld%lld" , &w[i] , &t[i]) , st += t[i];
    printf ("%lld" , (LL)(fans () * 1000));
    return 0;
}