给定 a1,⋯ ,ana_1,\cdots,a_na1 ,⋯,an 以及 b1,⋯ ,bnb_1,\cdots,b_nb1 ,⋯,bn ，求一组 xix_ixi ，使得： * ∑bxi≥W\sum b_{x_i}\ge W∑bxi ≥W * ∑axi∑bxi\dfrac{\sum a_{x_i}}{\sum b_{x_i}}∑bxi ∑axi 最大 求这个最大值，保留三位小数。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 显然是 01 分数规划。考虑二分，假设目前二分到 ttt，我们要判断是否有一组 xix_ixi ，使得 ∑axi∑bxi≥t\dfrac{\sum a_{x_i}}{\sum b_{x_i}}\ge t∑bxi ∑axi ≥t。 变形得 ∑(axi−t×bxi)≥0\sum (a_{x_i}-t\times b_{x_i})\ge 0 ∑(axi −t×bxi )≥0 类似于背包问题的方程。 以 WWW 为背包大小，bib_ibi 为物品重量，ai−t×bia_i-t\times b_iai −t×bi 为物品价值，跑 01 背包即可，dpWdp_WdpW 即为上式中的 ∑(axi−t×bxi)\sum (a_{x_i}-t\times b_{x_i})∑(axi −t×bxi )。