这题思路很简单,但是调试花了我一个下午……最后发现是一种情况没取 abs……(吐血)
题目链接:POJ 3977 Subset
Topcoder Single Round Match 616 Div 2 T3 题解
题目链接:CodeForces 294E Shaass the Great
这题真的太麻烦了……
0/1 分数规划是一种常见的模型:给你 n 个价值 $a_i$ 与 n 个代价 $b_i$,让你选出 m 个数字,使得 $ \sum \frac {a_i} {b_i} $ 最大。显然这种题目可以用二分,但是有一种更优秀的方法:Dinkelbach 迭代法。