emmm……看到题面“总才艺值与总体重的比值最大”，那么这个就是01分数规划问题了。 现在详细讲一讲如何解决这类问题。 先看简单一点的题： 有 n 个物品，有属性值 ai,bi要求选出至多 k 个物品，使得sum(ai) / sum(bi)尽可能大。 我们要首先二分答案 x，若 sum(ai) / sum(bi) ≥x 则说明答案可以更大。 稍微变形一下：sum(a[i]) >= sum(b[i]) * x; 继续：sum(a[i] - b[i] * x) >= x 我们发现 i 对答案的贡献是个常数 ai-bi了！ 由于至多选 k 个物品，我们可以贪心，将 ai-bix从大到小排...