51Nod 1257 背包问题 V3

1257 背包问题 V3

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示例

Output示例

3/4

不能用它们的比值来算，因为a/b+c/d!=(a+c)/(b+d).
可以用二分在做。
假设C（x）表示可以选择使得单位重量的价值不小于x。
那么单位重量的价值是：(p1+p2+....pk)/(w1+w2+...+wk)
因此判断(p1+p2+....pk)/(w1+w2+...+wk)>=x就可以了
即p1-w1*x+p2-w2*x+......pk-wk*x >= 0.而pi-wi*x的值进行贪心地进行选取，

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <string.h>
 4 #include <algorithm>
 5 #include <cmath>
 6 #define ll long long
 7 using namespace std;
 8 const int MAX = 50010;
 9 const int Inf = 1<<27;
10 int k,n;
11 struct Nod{
12     int w,p;
13     double a;
14 }nod[MAX];
15 bool cmp(Nod A, Nod B){
16     return A.a > B.a;
17 }
18 ll gcd(ll a, ll b){
19     return b==0?a:gcd(b,a%b);
20 }
21 int aa,bb,aaa,bbb;
22 bool C(double x){
23     for(int i = 0; i < n; i ++){
24         nod[i].a = nod[i].p-x*nod[i].w;
25     }
26     sort(nod,nod+n,cmp);
27     double sum = 0;
28     aa = bb =0;
29     for(int i = 0; i < k; i ++){
30         aa += nod[i].p;
31         bb += nod[i].w;
32         sum += nod[i].a;
33     }
34     return sum >= 0;
35 }
36 int main(){
37     scanf("%d %d",&n,&k);
38     for(int i = 0; i < n; i ++)
39         scanf("%d %d",&nod[i].w,&nod[i].p);
40     double l = 0, r = 1.0*Inf;
41     for(int i = 0; i < 100; i ++){
42         double m = (l+r)/2;
43         if(C(m)){
44             l=m;
45             aaa = aa;
46             bbb = bb;
47         }
48         else r = m;
49     }
50     printf("%lld/%lld
",aaa/gcd(aaa,bbb),bbb/gcd(aaa,bbb));
51     return 0;
52 }