01分数规划问题
所谓的01分数规划问题就是指这样的一类问题，给定两个数组，a[i]表示选取i的收益，b[i]表示选取i的代价。如果选取i，定义x[i]=1否则x[i]=0。每一个物品只有选或者不选两种方案，求一个选择方案使得$R =\frac{ \sum a_i * x_i }{ \sum b_i * x_i } $取得最值，即所有选择物品的总收益/总代价的值最大或是最小。
解法
对 $$R =\frac{ \sum a_i * x_i }{ \sum b_i * x_i } $$ 变形
得到等式 $$0 = \sum a_i*x_i - R * \sum b_i*x_i$$
令函数$$f(L) = \sum a_i*x_i - L * \sum b_i*x_i$$
整理得到$$f(L) = \sum (a_i - L * b_i) * x_i $$
显然$a_i - L * b_i$随L单调递减
若存在一种x数组的方案使$f(L) > 0$，则：
$$\sum a_i*x_i - L * \sum b_i*x_i > 0$$
即
$$\frac{ \sum a_i * x_i }{ \sum b_i * x_i } > L$$
即 R > L ， 存在更优解
当 f(L) = 0 时 R = L
当 f(L) < 0 时 无意义
Dinkelbash算法
直接贴代码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
using namespace std;
struct Data{
int a, b;
float d;
}da[MAXN];
bool cmp(Data a, Data b){
if (a.d > b.d) return true;
return false;
}
int n, m;
int main(){
freopen(""1.in"", ""r"", stdin);
freopen(""1.out"", ""w"", stdout);
while (true){
scanf(""%d%d"", &n, &m);
if (n == 0 && m == 0) break;
memset(da, 0, sizeof da);
for (int i = 1; i <= n; i++) scanf(""%d"", &da[i].a);
for (int i = 1; i <= n; i++) scanf(""%d"", &da[i].b);
//Dinkelbash Algorithm
float L = 1, Ans = 0;
while (abs(L - Ans) >= Eps) {
Ans = L;
for (int i = 1; i <= n; i++){
da[i].d = (float) da[i].a - L * (float) da[i].b;
}
sort(da + 1, da + 1 + n, cmp);
long long p = 0, q = 0;
for (int i = 1; i <= (n - m); i++){
p += (long long) da[i].a;
q += (long long) da[i].b;
}
L = (float) p / (float) q;
// cout << p << q << endl;
}
printf(""%.0lf\n"", Ans * 100);
}
return 0;
}