01分数规划基本问题
给出两个有 n n n 个元素的数组 a i a_i a i 和 b i b_i b i ,对于一组 $w_i\in \{0,1\}$,可能使得 $\Large{\frac{\sum\limits_{i=1}^n a_iw_i}{\sum\limits_{i=1}^n b_iw_i}}$ 取得最值,求这个最值。
求解——二分法
check函数
我们二分答案。假设要求的是最大值。
二分得到一个答案 x x x ,假设当前 x x x 小于最大值或者正好去到最大值,那么有 ∑ i = 1 n a i w i ∑ i = 1 n b i w i ⩾ x \frac{\sum\limits_{i=1}^n a_iw_i}{\sum\limits_{i=1}^n b_iw_i}\geqslant x i = 1 ∑ n b i w i i = 1 ∑ n a i w i ⩾ x ,即 ∑ i = 1 n w i ( a i − x b i ) ⩾ 0 \sum\limits_{i=1}^n w_i\left(a_i-xb_i\right)\geqslant 0 i = 1 ∑ n w i ( a i − x b i ) ⩾ 0 。如果经过检验,不存在∑ i = 1 n w i ( a i − x b i ) ⩾ 0 \sum\limits_{i=1}^n w_i\left(a_i-xb_i\right)\geqslant 0 i = 1 ∑ n w i ( a i − x b i ) ⩾ 0 的情况,即 $\max\left\{\sum\limits_{i=1}^n w_i\left(a_i-xb_i\right)\right\}<0$,那么就与假设矛盾,根据反证法的思想,说明 x x x 已经超过最大值。
模板
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 #include <iostream> #include <cstdio> #define N 100003 #define eps 1e-6 using namespace std;double a[N],b[N];inline bool check (double x) { int i; for (i=1 ;i<=n;i++) { if (a[i]-x*b[i]>=0 ) { return 1 ; } } return 0 ; } int main () { cin>>n; int i; for (i=1 ;i<=n;i++) scanf ("%lf" ,a+i); for (i=1 ;i<=n;i++) scanf ("%lf" ,b+i); double l=0 ,r=1e9 ; double ans=0 ; while (r-l>=eps) { double mid=(l+r)/2 ; if (check (mid)) { ans=l; l=mid; } else r=mid; } printf ("%.6lf\n" ,ans); return 0 ; }
例题
题目描述
wyh \text{wyh} wyh 学长现在手里有 n n n 个物品,这 n n n 个物品的重量和价值都告诉你,然后现在让你从中选取 k k k 个,问你在所有可能选取的方案中,最大的单位价值为多少(单位价值为选取的 k k k 个物品的总价值和总重量的比值)。
输入描述
输入第一行一个整数 T ( 1 ⩽ T ⩽ 10 ) T(1\leqslant T\leqslant 10) T ( 1 ⩽ T ⩽ 10 ) 。
接下来有 T T T 组测试数据,对于每组测试数据,第一行输入两个数 n n n 和 k k k ( 1 ⩽ k ⩽ n ⩽ 100000 ) (1\leqslant k\leqslant n\leqslant 100000) ( 1 ⩽ k ⩽ n ⩽ 100000 ) 。
接下来有 n n n 行,每行两个是 a a a 和 b b b ,代表这个物品的重量和价值。
输出描述
对于每组测试数据,输出对应答案,结果保留两位小数。
示例1
输入
1
3 2
2 2
5 3
2 1
输出
0.75
说明
对于样例来说,我们选择第一个物品和第三个物品,达到最优目的。
分析
设使得单位价值最大的 k k k 个物品的索引为 i 1 , i 2 , ⋯ , i k i_1,i_2,\cdots,i_k i 1 , i 2 , ⋯ , i k 。当二分得到一个答案 x x x ,假设 x x x 小于最大单位价值或恰好为最大单位价值,那么有 ∑ j = 1 k a i j b i j ⩾ x \sum\limits_{j=1}^k \frac{a_{i_j}}{b_{i_j}}\geqslant x j = 1 ∑ k b i j a i j ⩾ x ,即 $\sum\limits_{j=1}^k(a_{i_j}-xb_{i_j})\geqslant 0 $,若不存在 $\sum\limits_{j=1}^k(a_{i_j}-xb_{i_j})\geqslant 0 $ 的方案,即 $\max\left\{\sum\limits_{j=1}^k(a_{i_j}-xb_{i_j})\right\}< 0$,说明 x x x 大于最大值,右边界减小,否则 x x x 合法。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 #include <iostream> #include <algorithm> #include <cstdio> #define N 100003 #define eps 1e-6 using namespace std;int value[N],weight[N];double p[N];int n,k;bool check (double x) { int i; for (i=1 ;i<=n;i++) p[i]=value[i]-x*weight[i]; sort (p+1 ,p+1 +n,greater <double >()); double res=0 ; for (i=1 ;i<=k;i++) res+=p[i]; return res>=0 ; } int main () { int _; for (cin>>_;_;_--) { scanf ("%d%d" ,&n,&k); int i; for (i=1 ;i<=n;i++) scanf ("%d%d" ,weight+i,value+i); double l=0 ,r=1e9 ; double ans; while (r-l>=eps) { double mid=(l+r)/2 ; if (check (mid)) { ans=l; l=mid; } else r=mid; } printf ("%.2lf\n" ,ans); } return 0 ; }