N個物品的體積為W1，W2......Wn（Wi為整數(shù)），與之相對應(yīng)的價值為P1,P2......Pn（Pi為整數(shù)），從中選出K件物品（K <= N)，使得單位體積的價值最大。 Input 第1行：包括2個數(shù)N,?K(1?<=?K?<=?N?<=?50000) 第2?-?N?+?1行：每行2個數(shù)Wi,?Pi（1?<=?Wi,?Pi?<=?50000) Output 輸出單位體積的價值（用約分后的分數(shù)表示）。 Input示例 3?2 2?2 5?3 2?1 Output示例 3/4 ———————————————————————————— 第一眼看題目以為是貪心QAQ 后來發(fā)現(xiàn)不行 因為如果你現(xiàn)在已有的價值/體積是最佳 而現(xiàn)在有兩個價值很小的物品 a b a價值比b大 但是a的體積遠大于b的話 此時b肯定是更優(yōu)的 所以正解應(yīng)該是二分答案 判斷是否合法就好辣 #include<cstdio> #include<cstring> #include<algorithm> #define LL long long using namespace std; const int M=50007; int read(){int ans=0,f=1,c=getchar();while(c<'0'||c>'9'){if(c=='-') f=-1; c=getchar();}while(c>='0'&&c<='9'){ans=ans*10+(c-'0'); c=getchar();}return ans*f; } int n,k; int c[M],w[M]; LL sumx,sumy,ansx,ansy; LL gcd(LL x,LL y){while(y){LL p=x%y;x=y;y=p;} return x; } struct node{double v; int pos;}e[M]; bool cmp(node a,node b){return a.v-b.v>1e-6;} bool check(double mid){for(int i=1;i<=n;i++) e[i].v=1.0*w[i]-1.0*c[i]*mid,e[i].pos=i; sort(e+1,e+1+n,cmp);double sum=0; sumx=0; sumy=0;for(int i=1;i<=k;i++){sum+=e[i].v;sumx+=w[e[i].pos];sumy+=c[e[i].pos];}return sum>=0; } int main() {n=read(); k=read();for(int i=1;i<=n;i++) c[i]=read(),w[i]=read();double l=0,r=50000;while(r-l>1e-6){double mid=(l+r)/2;if(check(mid)) l=mid,ansx=sumx,ansy=sumy;else r=mid;}LL d=gcd(ansx,ansy);printf("%lld/%lld\n",ansx/d,ansy/d);return 0; } View Code

?

轉(zhuǎn)載于:https://www.cnblogs.com/lyzuikeai/p/7395789.html

總結(jié)

以上是生活随笔為你收集整理的1257 背包问题 V3——分数规划的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。