一开始人傻了,往背包套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背包即可。
0 条评论