一、题目概述

题意翻译

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

1. 所选奶牛总重量≥W\ge W≥W
2. 最大化比值∑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，优化思路：

1. 背包数组f[j]f[j]f[j]定义：总重量恰好为jjj时，∑vali\sum val_i∑vali​的最大值
2. 对于重量超过WWW的所有情况，统一合并存入f[W]f[W]f[W]：
   • 即当j+wi>Wj + w_i > Wj+wi​>W时，下标直接取WWW，不再记录更大重量
3. 最终只需要看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;}

执行流程：

1. 初始化数组为极小值，仅f[0]=0f[0] = 0f[0]=0（初始状态：0 重量 0 收益）
2. 枚举每一头奶牛，倒序遍历背包容量
3. 新重量超过WWW则压缩到下标WWW，更新该位置最大收益
4. 最终判断：所有总重量≥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)，数据范围下完全无超时风险

七、题型拆解与同类对比

1. 01 分数规划两类经典约束

• 固定选 k 件：POJ2976 Dropping tests → 排序贪心取前 n-k 项
• 重量下界 / 上界约束：本题 Talent Show → 结合 01 背包求解最值

2. 背包变形技巧拓展

• 重量上限限制：标准 01 背包，容量WWW，只存≤W\le W≤W的重量
• 重量下限限制：本题压缩超过WWW的重量统一存入f[W]f[W]f[W]，节省空间与计算量
• 同时有上下界：分段背包分别处理

八、踩坑避坑总结

1. 背包初始化：必须设为负无穷，不能初始 0，否则会误判不可达状态
2. 倒序遍历背包：01 背包标准要求，正序会变成完全背包，重复选牛
3. 重量压缩到WWW：不能直接开更大数组，否则空间超时
4. 浮点精度取整：输出前必须加极小偏移值，否则样例 / 边界数据会 WA
5. 二分分支方向：本题最大化比值，可行时更新左边界l=midl = midl=mid，不要写反

九、全文总结

模型核心

01 分数规划 + 变形 01 背包，是提高组二分 + DP 综合经典题

解题三步固定流程

1. 数学变形分式：构造vali=ti−x⋅wival_i = t_i - x \cdot w_ivali​=ti​−x⋅wi​
2. 浮点二分猜测比值xxx
3. 改造 01 背包处理「总重量≥W\ge W≥W」约束，判断最优收益是否≥0\ge 0≥0

应试价值

融合二分、动态规划、浮点精度三大考点，是 NOIP/CSP 提高组高频综合题型，熟练掌握可打通分数规划 + 背包类所有题目。