“空即是色，色即是空。”
用法
分数规划求一个分式的极值。
给出 $a_i$ 和 $b_i$ ，求一组 $w_i\in\{0,1\}$ ，最大化/最小化：
当然，毒瘤题中还会有一些特殊限制。
求解
二分
令当前答案为 $mid$ ，我们只需要使：（以最大值为例）
然后推得：
即可。最小值类似。
Dinkelbach 算法
Dinkelbach 算法的大概思想是每次用上一轮的答案当做新的 $L$ 来输入，不断地迭代，直至答案收敛。说实话，这东西我看了有 $5$ 篇讲解也不是太懂，之后有时间再学学。
有点类似于构造函数，通过对已知答案的迭代来得出当前答案。并根据更优解移动答案以逼近最优解。
例题
求最大分数，且需要满足 $\sum w_i\times b_i\ge W$ 的条件。
其实在开始的时候，就会发现 $w_i\in\{0,1\}$ 十分熟悉，有些像…… $01$ 背包。
把 $b_i$ 作为 $i$ 物品的重量，将 $a_i-mid\times b_i$ 作为第 $i$ 个物品的价值，作为 dp 来转移，求出 $dp[n][W]$ 即可。
将大于 $W$ 的 $\sum w_i\times b_i$ 直接视作 $W$ 即可。因为我们并不考虑实际重量和，只关心是否能把背包装满。
AC Code
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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
| #include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<iomanip>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#define gh() getchar()
#define re register
typedef long long ll;
using namespace std;
const int MAXN=301;
const int MAXW=1001;
const double eps=1e-5;
template<class T>
inline void read(T &x)
{
x=0;
char ch=gh(),t=0;
while(ch<'0'||ch>'9') t|=ch=='-',ch=gh();
while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=gh();
if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
read(x),read(x1...);
}
template<class T>
inline bool checkMax(T &x,T &y)
{
return x<y?x=y,1:0;
}
template<class T>
inline bool checkMin(T &x,T &y)
{
return x>y?x=y,1:0;
}
int a[MAXN],b[MAXN],W,N;
double dp[MAXW];
inline bool check(double x)
{
for(int i=1;i<=W;++i) dp[i]=-1e9;
for(int i=1;i<=N;++i)
for(int j=W;j>=0;--j)
{
int k=min(W,j+b[i]);
dp[k]=max(dp[k],dp[j]+a[i]-x*b[i]);
}
return dp[W]>0;
}
int main()
{
read(N,W);
for(int i=1;i<=N;++i) read(b[i],a[i]);
double l=0,r=1e9;
while(r-l>eps)
{
double mid=(l+r)/2;
if(check(mid)) l=mid;
else r=mid;
}
printf("%.0lf",floor(1000*l));
return 0;
}
|