一、题目概述题意翻译有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 头重量102030≥15102030 \ge 15102030≥15总才艺211132211132211132比值32/30≈1.0666632/30 \approx 1.0666632/30≈1.066661.06666×10001066.661.06666 \times 1000 1066.661.06666×10001066.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令每头牛的价值为valiti−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 00当前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]即当jwiWj w_i Wjwi​W时下标直接取WWW不再记录更大重量最终只需要看f[W]f[W]f[W]的最大值代表所有总重量≥W\ge W≥W的组合里∑vali\sum val_i∑vali​的最优值这样背包容量只需要开到WWW大幅降低时间、空间开销。背包转移公式遍历每一头奶牛倒序枚举容量01 背包防重复选取kmin⁡(W,jwi) k \min(W, j w_i)kmin(W,jwi​)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 代码#includebits/stdc.husingnamespacestd;intn,W,w[255],t[255];doublef[1005];boolcheck(doublex){// 初始化负无穷表示不可达for(inti1;iW;i)f[i]-1e9;f[0]0;for(inti1;in;i){// 01背包倒序枚举for(intjW;j0;j--){if(f[j]-1e9)continue;intkmin(W,jw[i]);f[k]max(f[k],f[j]t[i]-x*w[i]);}}returnf[W]0;}doublefind(){doublel0,r1000;// 精度1e-5满足×1000后取整无误差while(r-l1e-5){doublemid(lr)/2;if(check(mid))lmid;// 当前x可行放大左边界elsermid;}returnr;}intmain(){scanf(%d%d,n,W);for(inti1;in;i){scanf(%d%d,w[i],t[i]);}// 1e-8 规避浮点精度向下取整bugprintf(%d\n,int(find()*10001e-8));return0;}五、代码逐段分步讲解1. 全局变量定义intn,W,w[255],t[255];doublef[1005];n≤250n \le 250n≤250奶牛数量上限数组开 255 足够W≤1000W \le 1000W≤1000重量下界限制背包容量数组fff开到 1005double f[]存储对应重量下∑(ti−x⋅wi)\sum (t_i - x \cdot w_i)∑(ti​−x⋅wi​)的最大值浮点型适配二分的xxx2.check(x)二分判定函数核心背包boolcheck(doublex){for(inti1;iW;i)f[i]-1e9;f[0]0;// 重量0不选任何牛总和为0for(inti1;in;i){// 01背包倒序避免重复选取同一头牛for(intjW;j0;j--){if(f[j]-1e9)continue;intkmin(W,jw[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的组合最大收益是否大于 03.find()浮点二分主逻辑doublefind(){doublel0,r1000;while(r-l1e-5){doublemid(lr)/2;if(check(mid))lmid;elsermid;}returnr;}二分区间[0,1000][0, 1000][0,1000]才艺与重量比值最大不超过 1000精度阈值1e−51e-51e−5最终要放大 1000 倍该精度可以保证小数点后三位准确分支逻辑check(mid) true存在方案满足比值≥mid\ge mid≥mid更新左边界尝试更大比值check(mid) falsemidmidmid过大缩小右边界4.main输入输出与精度坑处理intmain(){scanf(%d%d,n,W);for(inti1;in;i){scanf(%d%d,w[i],t[i]);}// 1e-8 解决浮点向下取整误差printf(%d\n,int(find()*10001e-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]节省空间与计算量同时有上下界分段背包分别处理八、踩坑避坑总结背包初始化必须设为负无穷不能初始 0否则会误判不可达状态倒序遍历背包01 背包标准要求正序会变成完全背包重复选牛重量压缩到WWW不能直接开更大数组否则空间超时浮点精度取整输出前必须加极小偏移值否则样例 / 边界数据会 WA二分分支方向本题最大化比值可行时更新左边界lmidl midlmid不要写反九、全文总结模型核心01 分数规划 变形 01 背包是提高组二分 DP 综合经典题解题三步固定流程数学变形分式构造valiti−x⋅wival_i t_i - x \cdot w_ivali​ti​−x⋅wi​浮点二分猜测比值xxx改造 01 背包处理「总重量≥W\ge W≥W」约束判断最优收益是否≥0\ge 0≥0应试价值融合二分、动态规划、浮点精度三大考点是 NOIP/CSP 提高组高频综合题型熟练掌握可打通分数规划 背包类所有题目。