题目描述
这是一道模板题。
给你 n 个物品,每个物品有两个属性 ai 和 bi,求一组解 xi(1≤i≤n,xi=0 或 1) 使
Σi=1nbi×xiΣi=1nai×xi
最大,且恰好有 k 个 xi 为 1。
请求出这个最大值。
输入格式
第一行两个数,n,k。
第二行 n 个数,依次表示 a1,a2…an。
第三行 n 个数,依次表示 b1,b2…bn。
输出格式
一行,一个实数,精确到小数点后 4 位。
样例 1
5 3
1 2 4 1 2
4 3 9 3 7
0.4667
3 2
5 0 2
5 1 6
0.8333
10 6
1 5 3 7 2 8 5 4 2 6
15 35 12 12 9 15 7 7 13 15
0.4923
数据范围与提示
1≤k≤n≤105, 1≤ai≤bi≤106.