01分数规划问题，poj2976

本文主要是介绍01分数规划问题，poj2976，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

最近遇到了一类问题在翻阅大神博客后方知是01分数规划问题

感谢大神博客：http://blog.csdn.net/hhaile/article/details/8883652

解题思路：将公式化简F(L)=sigma(a[i]*x[i])-L*sigma(b[i]*x[i])，当确定一个L时，如果还有符合条件的L并且比原来的大，此时f》0，由于结果是1--100之内的数，所以最多需要找100次

In a certain course, you take n tests. If you get a_i out of b_i questions correct on test i, your cumulative average is defined to be

Given your test scores and a positive integer k, determine how high you can make your cumulative average if you are allowed to drop any k of your test scores.

Suppose you take 3 tests with scores of 5/5, 0/1, and 2/6. Without dropping any tests, your cumulative average is . However, if you drop the third test, your cumulative average becomes .

Input

The input test file will contain multiple test cases, each containing exactly three lines. The first line contains two integers, 1 ≤ n ≤ 1000 and 0 ≤ k < n. The second line contains n integers indicating a_i for all i. The third line contains n positive integers indicating b_i for all i. It is guaranteed that 0 ≤ a_i ≤ b_i ≤ 1, 000, 000, 000. The end-of-file is marked by a test case with n = k = 0 and should not be processed.

Output

For each test case, write a single line with the highest cumulative average possible after dropping k of the given test scores. The average should be rounded to the nearest integer.

Sample Input

Sample Output

83
100

Hint

To avoid ambiguities due to rounding errors, the judge tests have been constructed so that all answers are at least 0.001 away from a decision boundary (i.e., you can assume that the average is never 83.4997).

Source

Stanford Local 2005

ac代码：

#include <iostream>
#include <stdio.h>
#include <cstring>
#include <algorithm>
using namespace std;
int n,k;
int a[1002],b[1002];
double c[1002];
bool wo(double mid)
{
for(int i=0;i<n;i++)
c[i]=(double)a[i]-(double)b[i]*mid;
sort(c,c+n);
double sum=0;
for(int i=k;i<n;i++)
sum+=c[i];
return sum>0;
}
int main()
{
while(~scanf("%d%d",&n,&k))
{
if(n==0&&k==0)
break;
for(int i=0;i<n;i++)
scanf("%d",&a[i]);
for(int i=0;i<n;i++)
scanf("%d",&b[i]);
double l=0,r=1,mid;
for(int i=0;i<100;i++)
{
mid=(l+r)/2;
if(wo(mid))
l=mid;
else
r=mid;
}
printf("%d\n",(int)(100*mid+0.5));
}
return 0;
}