01分数规划基本问题

给出两个有 nn 个元素的数组 aia_i 和 bib_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函数

我们二分答案。假设要求的是最大值。
二分得到一个答案 xx，假设当前 xx 小于最大值或者正好去到最大值，那么有 ∑i=1naiwi∑i=1nbiwi⩾x\frac{\sum\limits_{i=1}^n a_iw_i}{\sum\limits_{i=1}^n b_iw_i}\geqslant x，即 ∑i=1nwi(ai−xbi)⩾0\sum\limits_{i=1}^n w_i\left(a_i-xb_i\right)\geqslant 0 。如果经过检验，不存在∑i=1nwi(ai−xbi)⩾0\sum\limits_{i=1}^n w_i\left(a_i-xb_i\right)\geqslant 0 的情况，即 $\max\left\{\sum\limits_{i=1}^n w_i\left(a_i-xb_i\right)\right\}<0$，那么就与假设矛盾，根据反证法的思想，说明 xx 已经超过最大值。

模板

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++)
	{
		/*若存在a[i]-x*b[i]非负
		那么若干非负的a[i]-x*b[i]之和
		必然非负
		即x必然为可行值
		*/
		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;//mid可行，更新最终答案
			l=mid;
		}
		else r=mid;//mid不可行，答案比mid小
	}
	printf("%.6lf\n",ans);
	return 0;
}

例题

牛客竞赛 NC15446 wyh\text{wyh} 的物品 ↬\looparrowright

题目描述

wyh\text{wyh} 学长现在手里有 nn 个物品，这 nn 个物品的重量和价值都告诉你，然后现在让你从中选取 kk 个，问你在所有可能选取的方案中，最大的单位价值为多少（单位价值为选取的 kk 个物品的总价值和总重量的比值）。

输入描述

输入第一行一个整数 T(1⩽T⩽10)T(1\leqslant T\leqslant 10)。
接下来有 TT 组测试数据，对于每组测试数据，第一行输入两个数 nn 和 kk(1⩽k⩽n⩽100000)(1\leqslant k\leqslant n\leqslant 100000)。
接下来有 nn 行，每行两个是 aa 和 bb，代表这个物品的重量和价值。

输出描述

对于每组测试数据，输出对应答案，结果保留两位小数。

示例1

输入
1
3 2
2 2
5 3
2 1
输出
0.75

说明

对于样例来说，我们选择第一个物品和第三个物品，达到最优目的。

分析

设使得单位价值最大的 kk 个物品的索引为 i1,i2,⋯ ,iki_1,i_2,\cdots,i_k。当二分得到一个答案 xx ，假设 xx 小于最大单位价值或恰好为最大单位价值，那么有 ∑j=1kaijbij⩾x\sum\limits_{j=1}^k \frac{a_{i_j}}{b_{i_j}}\geqslant 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$，说明 xx 大于最大值，右边界减小，否则 xx 合法。

代码

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;
	//前k大的value[i]-x*wight[i]之和即为最大值
	for(i=1;i<=k;i++) res+=p[i];
	return res>=0;//若非负则x合法
}
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;//mid合法，更新答案
				l=mid;
			}
			else r=mid;
		}
		printf("%.2lf\n",ans);
	}
	return 0;
}