P4377 [USACO18OPEN] Talent Show G｜01 分数规划 + 01 背包限制重量下界完整题解

发布时间：2026/7/8 9:36:19

一、题目概述

题意翻译

有nnn头奶牛，每头奶牛拥有重量wiw_iwi、才艺值tit_iti，选出一组奶牛满足两个条件：

所选奶牛总重量≥W\ge W≥W
最大化比值∑ti∑wi\frac{\sum t_i}{\sum w_i}∑wi∑ti（总才艺 / 总重量）

输出要求：将最优比值×1000\times 1000×1000后向下取整输出整数。

补充提示

浮点精度误差会导致本该为整数的结果算成略小的值，输出前需要加极小偏移避免取整出错。

样例解读

输入：

3 15 20 21 10 11 30 31

可选组合：

选第 1 头和第 2 头：重量10+20=30≥1510+20=30 \ge 1510+20=30≥15，总才艺21+11=3221+11=3221+11=32
比值32/30≈1.0666632/30 \approx 1.0666632/30≈1.06666
1.06666×1000=1066.661.06666 \times 1000 = 1066.661.06666×1000=1066.66，向下取整输出106610661066，与样例输出匹配

数据模型定位

分式最大化：标准 01 分数规划，使用浮点二分
约束条件：总重量至少WWW，不是恰好WWW，需要改造 01 背包处理下界限制

二、核心数学推导（分数规划）

我们二分猜测比值xxx，目标判断是否存在合法选牛方案满足：
∑ti∑wi≥x \frac{\sum t_i}{\sum w_i} \ge x∑wi∑ti≥x

两边同乘正数∑wi\sum w_i∑wi，变形得到判定不等式：
∑ti−x⋅∑wi≥0⇒∑(ti−x⋅wi)≥0 \sum t_i - x \cdot \sum w_i \ge 0 \Rightarrow \sum (t_i - x \cdot w_i) \ge 0∑ti−x⋅∑wi≥0⇒∑(ti−x⋅wi)≥0

令每头牛的价值为vali=ti−x⋅wival_i = t_i - x \cdot w_ivali=ti−x⋅wi，问题转化：

选出若干奶牛，总重量≥W\ge W≥W，使∑vali\sum val_i∑vali尽可能大，判断最大值是否≥0\ge 0≥0

最大值≥0\ge 0≥0：说明存在方案比值≥x\ge x≥x，可以尝试更大的xxx
最大值<0< 0<0：当前xxx过高，无法达到，需要缩小xxx

单调性成立，因此可以使用浮点二分逼近最优解。

三、特殊背包处理：总重量≥W\ge W≥W

常规 01 背包只能处理「总重量不超过WWW」，本题要求总重量至少WWW，优化思路：

背包数组f[j]f[j]f[j]定义：总重量恰好为jjj时，∑vali\sum val_i∑vali的最大值
对于重量超过WWW的所有情况，统一合并存入f[W]f[W]f[W]：
- 即当j+wi>Wj + w_i > Wj+wi>W时，下标直接取WWW，不再记录更大重量
最终只需要看f[W]f[W]f[W]的最大值：代表所有总重量≥W\ge W≥W的组合里，∑vali\sum val_i∑vali的最优值

这样背包容量只需要开到WWW，大幅降低时间、空间开销。

背包转移公式

遍历每一头奶牛，倒序枚举容量（01 背包防重复选取）：
k=min⁡(W,j+wi) k = \min(W, j + w_i)k=min(W,j+wi)
f[k]=max⁡(f[k],f[j]+ti−x⋅wi) f[k] = \max(f[k], f[j] + t_i - x \cdot w_i)f[k]=max(f[k],f[j]+ti−x⋅wi)

四、完整 AC 代码

#include<bits/stdc++.h>usingnamespacestd;intn,W,w[255],t[255];doublef[1005];boolcheck(doublex){// 初始化负无穷，表示不可达for(inti=1;i<=W;i++)f[i]=-1e9;f[0]=0;for(inti=1;i<=n;i++){// 01背包倒序枚举for(intj=W;j>=0;j--){if(f[j]==-1e9)continue;intk=min(W,j+w[i]);f[k]=max(f[k],f[j]+t[i]-x*w[i]);}}returnf[W]>0;}doublefind(){doublel=0,r=1000;// 精度1e-5，满足×1000后取整无误差while(r-l>1e-5){doublemid=(l+r)/2;if(check(mid))l=mid;// 当前x可行，放大左边界elser=mid;}returnr;}intmain(){scanf("%d%d",&n,&W);for(inti=1;i<=n;i++){scanf("%d%d",&w[i],&t[i]);}// +1e-8 规避浮点精度向下取整bugprintf("%d\n",int(find()*1000+1e-8));return0;}

五、代码逐段分步讲解

1. 全局变量定义

intn,W,w[255],t[255];doublef[1005];

n≤250n \le 250n≤250：奶牛数量上限，数组开 255 足够
W≤1000W \le 1000W≤1000：重量下界限制，背包容量数组fff开到 1005
double f[]：存储对应重量下∑(ti−x⋅wi)\sum (t_i - x \cdot w_i)∑(ti−x⋅wi)的最大值，浮点型适配二分的xxx

2.`check(x)`二分判定函数（核心背包）

boolcheck(doublex){for(inti=1;i<=W;i++)f[i]=-1e9;f[0]=0;// 重量0，不选任何牛，总和为0for(inti=1;i<=n;i++){// 01背包倒序，避免重复选取同一头牛for(intj=W;j>=0;j--){if(f[j]==-1e9)continue;intk=min(W,j+w[i]);f[k]=max(f[k],f[j]+t[i]-x*w[i]);}}// f[W]存储所有总重量≥W的最优总和returnf[W]>0;}

执行流程：

初始化数组为极小值，仅f[0]=0f[0] = 0f[0]=0（初始状态：0 重量 0 收益）
枚举每一头奶牛，倒序遍历背包容量
新重量超过WWW则压缩到下标WWW，更新该位置最大收益
最终判断：所有总重量≥W\ge W≥W的组合最大收益是否大于 0

3.`find()`浮点二分主逻辑

doublefind(){doublel=0,r=1000;while(r-l>1e-5){doublemid=(l+r)/2;if(check(mid))l=mid;elser=mid;}returnr;}

二分区间[0,1000][0, 1000][0,1000]：才艺与重量比值最大不超过 1000
精度阈值1e−51e-51e−5：最终要放大 1000 倍，该精度可以保证小数点后三位准确
分支逻辑：
- check(mid) = true：存在方案满足比值≥mid\ge mid≥mid，更新左边界，尝试更大比值
- check(mid) = false：midmidmid过大，缩小右边界

4.`main`输入输出与精度坑处理

intmain(){scanf("%d%d",&n,&W);for(inti=1;i<=n;i++){scanf("%d%d",&w[i],&t[i]);}// +1e-8 解决浮点向下取整误差printf("%d\n",int(find()*1000+1e-8));return0;}

重点细节：find() * 1000 + 1e-8
题目提示的精度 bug 解决方案：由于浮点存储存在微小误差，真实值 1.066 会被计算为 1.0659999999，直接转 int 会变成 1065；加上极小值10−810^{-8}10−8后修正误差，向下取整结果正确。

六、算法时间复杂度分析

浮点二分：循环约 50 次（区间 0~1000，精度1e−51e-51e−5）
单次背包：O(n×W)O(n \times W)O(n×W)，n≤250,W≤1000n \le 250, W \le 1000n≤250,W≤1000，单次仅 25 万次运算
总复杂度：O(50×n×W)O(50 \times n \times W)O(50×n×W)，数据范围下完全无超时风险