01分数规划

好久没发博客了……浅浅复活一下，讲个冷门些的算法。

算法目的：选出k组ai,bi使得   最大。

算法过程：

不妨考虑二分答案，那么答案的形式便是  的形式，则可通过移项转化为，进一步的，我们可以将求和合并，则有，这便是二分检验的条件，只需挑出满足条件的k组即可，该算法考不出太新鲜的，至多是二分加优化。

那么我们来看一道例题

P4377 [USACO18OPEN] Talent Show G

简化一下题意：选出任意组ai,bi使得最大，且。那么看到该限制条件，只需在二分时使用01背包优化即可。最后输出为答案*1000向下取整。

代码：

#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
using namespace std;
const int maxn=1e5+10;
int n,w,a[maxn],b[maxn];
double f[maxn]; 
bool check(double mid){for(int i=1;i<=w;i++) f[i]=-1e9;for(int i=1;i<=n;i++){for(int j=w;~j;j--){f[min(w,j+b[i])]=max(f[min(w,j+b[i])],f[j]+a[i]-mid*b[i]);}}return f[w]>=0;
}
int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n>>w;for(int i=1;i<=n;i++) cin>>b[i]>>a[i];double l=0,r=1e6;while(r-l>1e-4){double mid=(l+r)/2;if(check(mid)) l=mid;else r=mid;}cout<<(int)(1000*l)<<endl;return 0;
}