POJ 2976 Dropping tests 01分数规划 模板

Dropping tests

Time Limit: 1000MS Memory Limit: 65536K

Description

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

$$100*\frac{\sum_{i=1}^na_i}{\sum_{j=1}^nb_j}$$

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 $100*\frac{5+0+2}{5+1+6}=50$. However, if you drop the third test, your cumulative average becomes $100*\frac{5+0}{5+1}\approx 83.33$.

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 ai for all i. The third line contains n positive integers indicating bi for all i. It is guaranteed that 0 ≤ ai ≤ bi ≤ 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

3 1
5 0 2
5 1 6
4 2
1 2 7 9
5 6 7 9
0 0

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).

算法分析

所谓的01分数规划问题就是指这样的一类问题,给定两个数组,a[i]表示选取i的收益,b[i]表示选取i的代价。如果选取i,定义x[i]=1,否则x[i]=0。

每一个物品只有选或者不选两种方案,求一个选择方案即从其中选取k组a[i]/b[i],使得$R=\frac{\sum(a[i]*x[i])}{\sum(b[i]*x[i])}$取得最值,即所有选择物品的总收益/总代价的值最大或是最小。

01分数规划问题主要包含一般的01分数规划、最优比率生成树问题、最优比率环问题等。


来看目标式:

$$R=\frac{\sum(a[i]*x[i])}{\sum(b[i]*x[i])}$$

我们的目标是使得R达到最大或者最小,首先定义一个函数

$$F(L)=\sum(a[i]*x[i])-L*\sum(b[i]*x[i])$$

显然这只是对目标式的一个简单的变形。

分离参数,得到:

$$F(L)=\sum((a[i]-L*b[i])*x[i])$$

记$d[i]=a[i]-L*b[i]$,那么:

$$F(L)=\sum(d[i]*x[i])$$

接下来重点注意一下d[i]和F(L)的单调性。

如果我们已知了L,则所有的的d[i]是已知的,那么这里的贪心策略是为了得到一个最优的F(L),我们只需要将d[i]排序之后取其中的前k个或者后k个。也就是说,给定L,我们可以直接求出对应的F(L)。

接下来是F(L),因为b[i]是正的,显然F(L)对于L是单调递减的,这就启发我们可以通过某种方法把F(L)逼近至0,当F(L)=0时,即$\sum(a[i]*x[i])-L*\sum(b[i]*x[i])=0$,那么此时的L就是最优值。


然后还要注意到的问题是,我们每次贪心地取d[i]中最小的k个,则最终使得F(L)趋于0的L会是最小的比值;如果每次贪心地取d[i]中最大的k个,则最终使得F(L)趋于0的L会是最大的比值。

考虑$F(L)=\sum((a[i]-L*b[i])*x[i])$式中,我们取了最后k个d[i]使得F(L)=0,则如果用此时的L去取全部的数,F(L)_tot将是小于零的,也即使得整个F(L)_tot趋于0的L_tot是小于L的。故L是取K组数的情况下,最大的比值。(这段说的有点绕口)

另外再注意到的一点是,如果将a[i]与b[i]上下颠倒,求解的方法相同,结果跟颠倒前也是刚好相对应的。


最后又想到了一个关键点,k的值对最后的结果会是什么影响:

贪心地说,为了使结果尽可能的大,k也要尽可能的大,即尽可能多的舍弃一些,剩下选取的数越少,均值越大

总结F(L)的两个重要性质如下就是:

 1. F(L)单调递减

 2. F(max(L)/min(L)) = 0


之后的逼近方法可以有两种选择

1.二分法

二分区间,不断把F(L)逼近至0,若F(L)<0说明L过大,若F(L)>0说明L过小,直到逼近得到一个最优的L;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
/* ***********************************************
MYID : Chen Fan
LANG : G++
PROG : PKU_2976_Erfen
************************************************ */

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

#define eps 1e-6

using namespace std;

typedef struct nod
{
int a,b;
double r;
} node;

bool op(node a,node b)
{
return a.r>b.r;
}

node p[1010];

int main()
{
freopen("2976.txt","r",stdin);

int n,k;

while(scanf("%d%d",&n,&k))
{
if (n==0&&k==0) break;

for (int i=1;i<=n;i++) scanf("%d",&p[i].a);
for (int i=1;i<=n;i++) scanf("%d",&p[i].b);

int m=n-k;
double left=0,right=100;
while (left+eps<right)
{
double mid=(left+right)/2;
for (int i=1;i<=n;i++) p[i].r=p[i].a-mid*p[i].b;
sort(&p[1],&p[n+1],op);
double temp=0;
for (int i=1;i<=m;i++) temp+=p[i].r;
if (temp>0) left=mid;
else right=mid;
}

printf("%.0f\n",left*100);
}

return 0;
}

2.Dinkelbach

从另外一个角度考虑,每次给定一个L,除了我们用来判定的F(L)之外,我们可以通过重新计算得到一个L’,而且能够证明L’一定是更接近最优解的,那么我们可以考虑直接把L移动到L’上去。当L=L’时,说明已经没有更接近最优的解了,则此时的L就是最优解。

注意在Dinkelbach算法中,F(L)仍然是判定是否更接近最优解的工具,也即此时d[i]的选择仍然与之前相同,只是最后移动解的时候是把L直接移往L’

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
/* ***********************************************
MYID : Chen Fan
LANG : G++
PROG : PKU_2976_Dinkelbach
************************************************ */

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>

#define eps 1e-6

using namespace std;

typedef struct nod
{
int a,b,index;
double r;
} node;

bool op(node a,node b)
{
return a.r>b.r;
}

node p[1010];

int main()
{
freopen("2976.txt","r",stdin);

int n,k;

while(scanf("%d%d",&n,&k))
{
if (n==0&&k==0) break;

for (int i=1;i<=n;i++) scanf("%d",&p[i].a);
for (int i=1;i<=n;i++) scanf("%d",&p[i].b);

int m=n-k;
double l=0,temp=1;
while (fabs(l-temp)>=eps)
{
l=temp;
for (int i=1;i<=n;i++) p[i].r=p[i].a-l*p[i].b;
sort(&p[1],&p[n+1],op);
int x=0,y=0;
for (int i=1;i<=m;i++)
{
x+=p[i].a;
y+=p[i].b;
}
temp=(double)x/y;
}

printf("%.0f\n",temp*100);
}

return 0;
}
0%