# 0/1分数规划()-其他

## 0/1分数规划()

### 0/1分数规划

$$0/1$$分数规划模型是指，给定:$$a_1\sim a_n,b_1\sim b_n$$,要构造$$x_1\sim x_n(\forall i\in[1,n],x_i=0\text{或}1)$$

int a[1005],n,b[1005],k;
double c[1005],l,r,mid;
const double eps=1e-8;
bool check(){
for(int i=1;i<=n;i++){
c[i]=a[i]-mid*b[i];
}
sort(c+1,c+n+1);
double ans=0;
for(int i=k+1;i<=n;i++)ans+=c[i];
return ans>=0;//true:应该扩大
}
int main(){
while(1){
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
for(int i=1;i<=n;i++)scanf("%d",&b[i]);
if(n==0&&k==0)return 0;
l=0,r=1;
while(r-l>eps){
mid=(l+r)/2;
if(check())l=mid;
else r=mid;
}
printf("%d\n",(int)(mid*100+0.5));
}
}

————————

### 0/1分数规划

$$0/1$$分数规划模型是指，给定:$$a_1\sim a_n,b_1\sim b_n$$,要构造$$x_1\sim x_n(\forall i\in[1,n],x_i=0\text{或}1)$$

int a[1005],n,b[1005],k;
double c[1005],l,r,mid;
const double eps=1e-8;
bool check(){
for(int i=1;i<=n;i++){
c[i]=a[i]-mid*b[i];
}
sort(c+1,c+n+1);
double ans=0;
for(int i=k+1;i<=n;i++)ans+=c[i];
return ans>=0;//true:应该扩大
}
int main(){
while(1){
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
for(int i=1;i<=n;i++)scanf("%d",&b[i]);
if(n==0&&k==0)return 0;
l=0,r=1;
while(r-l>eps){
mid=(l+r)/2;
if(check())l=mid;
else r=mid;
}
printf("%d\n",(int)(mid*100+0.5));
}
}