Yougth的最大化

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <cmath>
 5 
 6 using namespace std;
 7 
 8 #define N 10010
 9 
10 double w[N],v[N],ave[N];
11 int k,n;
12 double max1;
13 
14 int check(double x)
15 {
16     double sum=0;
17     for(int i=0;i<n;i++)
18     {
19         ave[i]=v[i]-w[i]*x;
20     }
21     sort(ave,ave+n);
22     for(int i=0;i<k;i++)
23         sum+=ave[n-1-i];
24      return sum>=0;
25 } 
26 
27 
28 double  reseach()
29 {
30     double l=0,r=max1,mid;
31     for(int i=0;i<100;i++)
32     {
33         mid=(l+r)/2;
34         if(check(mid))
35             l=mid;
36         else
37             r=mid;
38     }
39     return l;
40 }
41 int main()
42 {
43     while(~scanf("%d%d",&n,&k))
44     {
45         max1=0;
46         for(int i=0;i<n;i++)
47         {
48             scanf("%lf%lf",&w[i],&v[i]);
49             if(max1<v[i]/w[i])
50                 max1=v[i]/w[i];
51         }
52         printf("%.2lf
",reseach());
53     }
54     return 0;
55 }
56

View Code

这道题目是一道0-1分数规划求最优值。

方法是一个二分搜索+贪心的题目。

出这道题目就是告诉大家二分不仅可以查找，还可以搜索一个更优值。

要使得单位重量的价值最大，则其最大不超过单个中最大的单位重量的价值，最小当然不小于0.

那么我们就这一在0--最大单位重量的价值中间找一个值ans，使得ans为满足题目条件的最大值。如果满足条件，则可以找更大的。设置一个条件。既二分搜索、

从n个物品中找k个使得k个的价值和/质量和>=ans

为了使得ans尽可能的大，那么这里就要贪心选择。

代码详见：