0/1分数规划

1.0/1分数规划模板

例题：poj2976

二分求解M，M即为答案

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
struct Pair{
	int a,b;double y;
}p[1005];
bool cmp(Pair a,Pair b){
	return a.y>b.y;
}
int n,k;
bool check(double x){
	for(int i=0;i<n;i++)p[i].y=p[i].a*1.0-x*p[i].b;
	sort(p,p+n,cmp);
	double f=0;
	for(int i=0;i<k;i++)f+=p[i].y;
	return f<0;
}
int main(){
        ios::sync_with_stdio(false);cin.tie(0);
	while(cin>>n>>k&&n+k){
		k=n-k;
		for(int i=0;i<n;i++)cin>>p[i].a;
		for(int i=0;i<n;i++)cin>>p[i].b;
		double l=0,r=0;
		for(int i=0;i<n;i++)r+=p[i].a;
		for(int i=0;i<50;i++){
			double mid=l+(r-l)/2.0;
			if(check(mid))r=mid;
			else l=mid;
		}
		printf("%d\n",(int)(100*(l+0.005)));
	}
	return 0;
}

2.最优比率背包

例题：洛谷P4377

本题有Σw_is_i>=w的限制，其余就是最优比率背包的模板了

#include<bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f,N = 255,WW = 1e3+5;
struct x{int w,t;double y;}cow[N];
double dp[WW];
int n,W;
bool check(double x){
	int i,j;
	for(i=1;i<=n;i++)cow[i].y=(double)cow[i].t-x*cow[i].w;
	for(i=1;i<=W;i++)dp[i]=-INF;dp[0]=0;
	for(i=1;i<=n;i++){
		for(j=W;j>=0;j--){
			if(j+cow[i].w>W)dp[W]=max(dp[W],dp[j]+cow[i].y);
			else dp[j+cow[i].w]=max(dp[j+cow[i].w],dp[j]+cow[i].y);
		}
	}
	return dp[W]<0;
}
int main(){
	cin>>n>>W;
	for(int i=1;i<=n;i++)cin>>cow[i].w>>cow[i].t;
	double l=0,r=0;for(int i=1;i<=n;i++)r+=cow[i].t;
	for(int i=0;i<50;i++){
		double mid=l+(r-l)/2.0;
		if(check(mid))r=mid;
		else l=mid;
	}
	cout<<(int)(l*1000);
	return 0;
}