[POJ2976]Dropping tests

附言

不得不吐槽POJ,注意这种题目的printf控制符一定要注意,还有四舍五入可能会带来的误差,而且double输出时一定要对应 %f
卡了我好半天 T^T

 

题目

题目链接,题目大意是,给你你 na_ib_i 。挑选出 k 组出来,最后得到的分数为    求最大的分数位多少。

 

01分数规划

这题可以用01分数规划来写。01分数规划就是指收益函数为

P\ =\ \frac{\sum_i A_i}{\sum_i B_i}

这样一类的问题。

 

二分答案法

首先我们不妨设答案是 Q,每一个二元组 (A_i,\ B_i) 最后是否加入到决策中的状态是 X_i,显然 X_i 的状态有0,1两种。那么,我们的收益函数就可以写成

P\ =\ \frac{\sum_i A_i*X_i}{\sum_i B_i*X_i}


因为我们设 Q 为答案,也就是最大的收益,那么我能可以肯定的一点是,对于任意的 X_i 的组合,一定有

P\ =\ \frac{\sum_i A_i*X_i}{\sum_i B_i*X_i} \ <=\ Q


也就是说

{\sum_i A_i*X_i} \ <=\ Q\ *\ {\sum_i B_i*X_i}


再化简得

\sum_i {(A_i\ -\ Q*B_i)\ *\ X_i} \ <=\ 0


这样的话,我们可以先假设出一个答案 R ,先不管这个答案是否能存在,我们先算出 \sum_i {(A_i\ -\ Q*B_i)\ *\ X_i},如果这个值可以存在大于0的话,那么肯定会有一个更优解存在。如果小于0那么最优解一定比 R 小。因为我们只关心是否这个值是否可以大于0,所以直接贪心,将 (A_i\ -\ Q*B_i) 从大到小排序,取前几个作为决策,就可以知道是否可以大于0了。
知道了如何判别一个解是否最优,且解之间还存在单调的关系,那么我就可以二分答案了。
具体可以看一看代码。

代码

 

其他

其实二分法求01分数规划问题还是挺简单的,关键是要理解数学推理过程,Dinkelbach算法请看下面的文章。 🙂

 

完结

One thought on “[POJ2976]Dropping tests

  1. Pingback: Dinkelbach算法 实例 | 火药

发表评论

电子邮件地址不会被公开。 必填项已用*标注