附赠题目链接：\(\text{51Nod-1257}\)
目录\(\text{description}\)
\(n\) 个物品的体积为 \(w_1,w_2,\cdots,w_n\)（\(w_i\) 为整数），与之相对应的价值为 \(p_1,p_2,\cdots,p_n\)（\(p_i\) 为整数），从中选出 \(k\) 件物品（\(k\le n\)），使得单位体积的价值最大。
\(\text{sol}\)
对于题目中的单位体积的价值可以理解为：
\[\max\left\{\frac{\sum_{i=1}^{k}p_i}{\sum_{i=1}^{k}w_i}\right\} \]其中 \(p_i\) 的选取同时会影响到分子和分母的大小，从而影响最终答案，因此无法进行贪心选择。
通过 \(01\) 分数规划解决问题，将原本的问题进行转换。
首先令答案为 \(x\)，那么有 \(x=\left(\sum_{i=1}^{k}p_i\right){/}\left(\sum_{i=1}^{k}w_i\right)\)。
将其修改得到其变式为
\[\sum_{i=1}^{k}p_i-x\sum_{i=1}^{k}w_i=0 \]那么就是说这个答案 \(x\) 是一定存在一个方案使得上述式子为 \(0\)。
由此，假如一个 \(x'\) 使得上述公式的最大值大于 \(0\) 的话，就表示还有更优的答案 \(x\)，相反同理。
那么就可以考虑二分答案，将每个物品的权值看作 \(p_i-x\times w_i\)。
这时候我们只需要选择 \(k\) 个数，判断其最大值是否大于 \(0\) 即可，此时可以选择贪心求解。
\(\text{CODE}\)
//
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const double eps=1e-5;
double l,r,d[100100],tmp;
int a[100100],b[100100],tmpk[100100];
int tmpp,tmpq,n,k,fq,fp,fk;
int gcd(int a,int b) {
while(b^=a^=b^=a%=b);
return a;
}
bool check(double x) {
tmp=0.00; tmpp=tmpq=0;
for(int i=1;i<=n;i++) {
d[i]=1.00*a[i]-1.00*b[i]*x;
tmpk[i]=i;
}
sort(tmpk+1,tmpk+1+n,[](int x,int y){
return d[x]>d[y];
});
for(int i=1;i<=k;i++) {
tmp+=d[tmpk[i]];
tmpq+=a[tmpk[i]];
tmpp+=b[tmpk[i]];
}
return tmp>=eps;
}
int main() {
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++) {
scanf("%d%d",&b[i],&a[i]);
}
l=0.00; r=100000.00;
while(r-l>eps) {
double mid=(l+r)/2.00;
if(check(mid)) {
l=mid;
fq=tmpq; fp=tmpp;
}
else r=mid;
}
fk=gcd(fq,fp);
printf("%d/%d",fq/fk,fp/fk);
return 0;
}
\(\text{Else}\)
在判断二分的答案是否合法的时候，有时候需要选择不只是贪心的其他方法，例如：动规等。
同样的是一道入门题：Dropping tests
涉及到树上问题的 \(01\) 规划：规划
标签：fp,fq,01,入门,int,text,sum,V3,include From： https://www.cnblogs.com/Cnghit/p/17484727.html