P2989 [USACO10MAR] Need For Speed S

Bassie正在为即将到来的赛车比赛作准备。 她有一辆赛车，重为M，且可以提供F的力。 现在她想要给这辆赛车安装一些零件（总共有N个零件），每个零件具有属性$M_i$和$F_i$，表示其重量以及可以提供的力。 设$X_i = 1\text{或}0$，表示第i个零件选或不选。 最大化$\frac{F+\sum_{i=1}^{n}X_i \times F_i}{M+\sum_{i=1}^{n}X_i \times M_i}$; 在此基础上最小化$\sum_{i=1}^{n}X_i \times M_i + M$。

无

无