01 分数规划小结
发布时间:2020-12-14 04:18:22 所属栏目:大数据 来源:网络整理
导读:01分数规划是用来解决这样的一类问题: 有一堆物品,每一个物品有一个收益ai,一个代价bi,我们要求一个方案使选择的∑ai/∑bi最大。 这一类问题一般都有固定套路: 我们令x=∑ai/∑bi,我们要最大化x。 稍微改变一下得到:∑(ai-bi*x)=0。 即我们需满足这
01分数规划是用来解决这样的一类问题: 这一类问题一般都有固定套路: 看一道板子:bzoj 5281 Talent Show #include <bits/stdc++.h> using namespace std; inline int gi () { int x=0,w=0; char ch=0; while (! (ch>=‘0‘ && ch<=‘9‘) ) { if (ch==‘-‘) w=1; ch=getchar (); } while (ch>=‘0‘ && ch<=‘9‘) { x= (x<<3) + (x<<1) + (ch^48); ch=getchar (); } return w?-x:x; } const int N=251; int n,W,l,r=100000,Mid,wi[N],val[N]; long long f[100010]; bool Check (int Val) { memset (f,0xcf,sizeof (f) ); f[0]=0; for (int i=1;i<=n;++i) for (int j=W;j>=0;--j) { int k=min (j+wi[i],W); f[k]=max (f[k],f[j]+val[i]- (long long) wi[i]*Val); } return f[W]>=0; } int main () { n=gi (),W=gi (); for (int i=1;i<=n;++i) { wi[i]=gi (),val[i]=gi (); val[i]*=1000; } while (l<r) { Mid= (l+r+1) >>1; if (Check (Mid) ) l=Mid; else r=Mid-1; } printf ("%dn",l); return 0; } ? 另外一道板子:bzoj 4753 最佳团体 #include <bits/stdc++.h> using namespace std; inline int gi () { int x=0,w=0; char ch=0; while (! (ch>=‘0‘ && ch<=‘9‘) ) { if (ch==‘-‘) w=1; ch=getchar (); } while (ch>=‘0‘ && ch<=‘9‘) { x= (x<<3) + (x<<1) + (ch^48); ch=getchar (); } return w?-x:x; } const int N=2510; const double Eps=1e-5; int n,K,tot,head[N],Size[N]; double l,r=20000,Val[N],Pay[N],f[N][N]; struct Edge { int next,now; }e[N]; inline void Make (int from,int to) { e[++tot].next=head[from]; head[from]=tot; e[tot].now=to; } void DP (int x) { Size[x]=1; f[x][0]=0; f[x][1]=Val[x]-Pay[x]*Mid; for (int i=head[x];i;i=e[i].next) { int y=e[i].now; DP (y); for (int i=Size[x];i>=1;--i) for (int j=Size[y];j>=0;--j) f[x][i+j]=max (f[x][i+j],f[x][i]+f[y][j]); Size[x]+=Size[y]; } } bool Check () { memset (f,0xc2,sizeof (f) ); memset (Size,0,sizeof (Size) ); DP (0); if (f[0][K+1]>0) return 1; return 0; } int main () { K=gi (),n=gi (); for (int i=1,Pre;i<=n;++i) { scanf ("%lf%lf",&Pay[i],&Val[i]); Pre=gi (); Make (Pre,i); } while (r-l>=Eps) { Mid= (l+r) /2.0; if (Check () ) l=Mid; else r=Mid; } printf ("%.3lfn",l); return 0; } ? 可以发现(个人感觉huaji)01分数规划是和背包紧密相连的。。 (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |