# 0/1 分数规划与 Dinkelbach 迭代法

0/1 分数规划是一种常见的模型：给你 n 个价值 a_i 与 n 个代价 b_i，让你选出 m 个数字，使得 \sum \frac {a_i} {b_i} 最大。显然这种题目可以用二分，但是有一种更优秀的方法：Dinkelbach 迭代法。

## 例题：最大化平均值

### 样例输入输出

#### 样例输入

3 2
2 5 2
2 3 1


#### 样例输出

0.75


### 约定

1<=k<=n<=500000,1<=wi,vi<=10^6

## 用二分法解

\displaystyle \frac {v_1+v_2+\dots+v_k} {w_1+w_2+\dots+w_k} \leqslant ans \\
\iff \sum_{i=1}^{n} v_i-ans \ast w_i \geqslant 0 \\
\iff \sum_{i=1}^{n} v_i – \sum_{i=1}^{n} ans \ast w_i \geqslant 0

### 参考代码

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=10005;
int n,m,w[maxn],v[maxn];
double ans,q[maxn];
inline bool cmp(double x,double y){
return x>y;
}
inline bool check(double x){
for (int i=1;i<=n;i++) q[i]=(double)v[i]-(double)w[i]*x;
sort(q+1,q+1+n,cmp);
double cnt=0.0;
for (int i=1;i<=m;i++) cnt+=q[i];
return cnt>=0.0;
}
int main(){
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++) scanf("%d",&w[i]);
for (int i=1;i<=n;i++) scanf("%d",&v[i]);
double L=1e-8,R=1e8;
while (R-L>1e-5){
double mid=(L+R)/2.0;
if (check(mid)){
ans=mid;L=mid+1e-5;
} else R=mid-1e-5;
}
printf("%.2f\n",ans);
return 0;
}


## Dinkelbach 迭代法

（如果不懂，看看代码就理解了）

### 参考代码

// Dinkelbach Iterative ALgorithm
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=500005;
const double eps=1e-7;
int n,m,w[maxn],v[maxn];
struct TempData{
double x;
int id;
}a[maxn];
double ans=1e7;
inline double myabs(double x){
if (x<0) return -x; else return x;
}
int ret=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}
while (ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
return ret*f;
}
inline bool cmp(TempData aa,TempData bb){
return aa.x>bb.x;
}
int main(){
double now=(double)(rand()%n);
while (myabs(now-ans)>eps){
ans=now;
for (int i=1;i<=n;i++) a[i].x=(double)v[i]-(double)w[i]*ans,a[i].id=i;
sort(a+1,a+1+n,cmp);
double sum_w=0.0,sum_v=0.0;
for (int i=1;i<=m;i++){
sum_w+=w[a[i].id];
sum_v+=v[a[i].id];
}
now=sum_v/sum_w;
}
printf("%.2f\n",ans);
return 0;
}