51nod 1257 01分数规划/二分

http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1257

1257 背包问题 V3

基准时间限制：3 秒 空间限制：131072 KB 分值: 80 难度：5级算法题

收藏

关注

N个物品的体积为W1，W2......Wn（Wi为整数），与之相对应的价值为P1,P2......Pn（Pi为整数），从中选出K件物品（K <= N)，使得单位体积的价值最大。

Input

第1行：包括2个数N, K(1 <= K <= N <= 50000)

第2 - N + 1行：每行2个数Wi, Pi（1 <= Wi, Pi <= 50000)

Output

输出单位体积的价值（用约分后的分数表示）。

Input示例

3 2

2 2

5 3

2 1

Output示例

3/4
  第一次写分数规划，感觉就是数学真神奇- -
  假设我们已知选了k件，他们的单位价值就是 x = ∑(pi) / ∑(wi) , 分解一下得到 ∑(pi) - x*∑(wi) = 0 ,对于所有合法的x这个式子肯定成立，所以对于max {x}也是，
我们有 ∑(pi) - x1*∑(wi) = 0 , 如果 x1==max(x) ,显然x1就是最大值 ； 如果x1<max(x)则他不是最优解 ； 如果x1>max(x) 这个式子<0说明不合法。
只要二分一下x的值就好了，为了使得x尽量合法显然我们将所有的 pi-x*wi排序之后优先选择较大的即可。

 #include<iostream>

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 using namespace std;

 #define LL long long

 int W[], P[];

 struct node { double d;int u; }D[];

 bool cmp(node A, node B) { return A.d < B.d; }

 int gcd(int a, int b) { return b ==  ? a : gcd(b, a%b); }

 bool ok(double x, int N, int K, int &a, int &b)

 {

     for (int i = ;i <= N;++i) {

         D[i].d = 1.0*P[i] - x*W[i];

         D[i].u = i;

     }

     sort(D + , D +  + N,cmp);

     double s = ; int w1 = , p1 = ;

     for (int i = N;i > N - K;i--) {

         s += D[i].d;

         w1 += W[D[i].u];

         p1 += P[D[i].u];

     }

     if (s >= ) {

         int y = gcd(w1, p1);

         a = w1 / y;

         b = p1 / y;

     }

     return s >= ;

 }

 int main()

 {

     int N, K, i, j, k;

     cin >> N >> K;

     for (i = ;i <= N;++i)

     {

         scanf("%d%d", W + i, P + i);

     }

     double l = , r = ;

     int w,p;

     while (r - l >= 1e-) {

         double mid = r - (r - l) / ;

         if (ok(mid,N,K,w,p)) {

             l = mid;

         }

         else {

             r = mid;

         }

     }//cout << l << endl;

     printf("%d/%d\n",p,w);

     return ;

 }