01分数规划

先上基本模板后面慢慢更新

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <math.h>
#include <string.h>
#include <queue>
#include <string>
#define LL long long
#define _LL __int64
#define eps 1e-7
using namespace std;
const _LL INF = 1e18;
const int maxn = 1010;

int n,k;
int a[maxn],b[maxn];
double c[maxn];

int main()
{
while(~scanf("%d %d",&n,&k) && (n || k))
{
for(int i = 1; i <= n; i++)
scanf("%d",&a[i]);
for(int i = 1; i <= n; i++)
scanf("%d",&b[i]);

double l = 0.0;
double r = 1.0;
double mid;

while(fabs(r-l) > eps)
{
mid = (l+r)/2;

for(int i = 1; i <= n; i++)
c[i] = 1.0*a[i] - mid * 1.0 * b[i];
sort(c+1,c+1+n);
double sum = 0.0;
for(int i = k+1; i <= n; i++)
sum += c[i];
if(sum > 0)
l = mid;
else if(sum < 0)
r = mid;
else break;
}
mid = mid*100;
printf("%.0f\n",mid);
}
return 0;
}

01分数规划

原文：https://www.cnblogs.com/hgangang/p/11517952.html