一开始人傻了,往背包套0/1分数规划。


其实题目就是一个有限制条件的0/1分数规划。

但是前提它是一个分数规划,那么我们来分析一下题意。

让我们求$\frac{\sum P_ix_i}{\sum S_ix_i}$,可以尝试二分答案$C$。

若$\frac{\sum P_ix_i}{\sum S_ix_i}\ge C$,则有$\sum P_ix_i-C*S_ix_i\ge 0$

反之,有$\sum P_ix_i-C*S_ix_i< 0$

可以根据这个条件二分答案后,把点权设为$P_i-C*S_i$,再套一个0/1背包即可。