首页 > 代码库 > 最大化平均值

最大化平均值

2024-07-29 22:08:24   224人阅读

n个物品的重量和价值分别是wi和vi。从中选取k个物品使单位重量的价值最大

输入

n = 3

k = 2

(w, v) = { (2, 2), (5, 3), (2, 1) }

输出

0.75（选择0和2号物品，平均价值是(2+1)/(2+2) = 0.75）

一般最先想到的方法可能是把物品按照单位价值排序，从大到小贪心的选取。但是这个方法对于样例得到结果是5/7 = 0.714。

实际上，对于这个问题使用二分搜索法可以很好的解决。我们定义

条件C(x):=可以选择使单位重量的价值不小于x

因此原问题就变成求满足C(x)的最大x。假设我们选了某个物品的集合S，那么它们的单位重量价值为

∑vi / ∑wi

因此变成判断是否存在S满足下面的条件

∑vi / ∑wi >= x，即 ∑(vi - x * wi) >= 0

因此，可以对(vi - x * wi)进行排序贪心地选取

C(x) = （(vi - x * wi)从大到小排列中的前k个的和不小于0）

每次判断的复杂度为O(nlogn)。

 1 #include <iostream> 2 #include <algorithm> 3 #include <cstdio> 4 using namespace std; 5  6 #define INF        1000 7 #define MAX_N    1000 8  9 int n, k;10 int w[MAX_N], v[MAX_N];11 double y[MAX_N];12 13 //判断是否满足条件14 bool C(double x)15 {16     for (int i = 0; i < n; i++)17     {18         y[i] = v[i] - x * w[i];19     }20     sort(y, y+n);21 22     //计算y数组中从大到小前k个数的和23     double sum = 0;24     for (int i = 0; i < k; i++)25     {26         sum += y[n-i-1];27     }28     return sum >= 0;29 }30 31 void solve()32 {33     double lb = 0, ub = INF;34     for (int i = 0; i < 100; i++)35     {36         double mid = (lb + ub) / 2;37         if (C(mid)) lb = mid;38         else ub = mid;39     }40     printf("%.2f\n", ub);41 }42 43 44 int main()45 {46     cin >> n >> k;47     for (int i = 0; i < n; i++)48     {49         cin >> w[i] >> v[i];50     }51     solve();52     return 0;53 }

 

最大化平均值


联系
我们