01 分数规划

LittleDrinks · 2023-06-23 00:32:11 · 算法·理论

01 分数规划

参考oi-wiki

定义及做法

01 分数规划，求 f=\frac{\displaystyle\sum^n_{i=1}{a_i\times w_i}}{\displaystyle\sum^n_{i=1}{b_i\times w_i}} 的最小值或最大值，其中 w_i=\begin{cases}0 & choose\\ 1 & not \ choose\end{cases}。做法是二分答案。

限制选择个数的情况

例： POJ-2976，AC代码提交记录（题外话：POJ 太**了……）

此处以最大值为例，假设在二分答案的过程中，现在考虑 k 是否为最大值。

若 k 不是最大值，即存在一组 w 使得 f\geq k，即 k\leq f_{max}。

将 f 展开，不妨记作 \displaystyle\frac{\sum a}{\sum b}\geq k，移项得 \sum a-k\times \sum b\geq 0。

也就是说，只要满足 \sum a-k\times \sum b\geq 0，就能说明 k\leq f_{max}，k 不是最大值。

根据这一点，可以设 c_i=a_i-k\times b_i，在限制选择 m 个的情况下，可以贪心，按照 c 从大到小选择 m 个，令 w=1。

排序选择后，有 \displaystyle\sum^m_{i=1}c_i=\displaystyle\sum^m_{i=1}\{a_i-k\times b_i\}=\displaystyle\sum^m_{i=1}\{a_i\}-k\times\displaystyle\sum^m_{i=1}\{b_i \}。

也就是说，如果 \displaystyle\sum^m_{i=1}c_i\geq 0，那么有 k\leq f_{max}，把这个作为 check() 函数，然后据此二分即可。 时间复杂度 O(n \log n)。

限制 \sum b\geq B 的情况

例：洛谷P4377，AC代码提交记录

和上面不同的是，对于 c_i=a_i-k\times b_i，不能从大到小选择，因为这样没有将 \sum b 纳入考虑范围。

一种可行的做法是 01 背包。

注意这里 \sum b 会大于题目给定的 B 的范围，可能爆空间，需要将状态转移方程中 w-b_i 换为 w+b_i：

当 w+b_i\geq B 的时候，一律当作 B 做。不妨设 x=min\{B,w+b_i\}，则状态转移方程可以化简为：

进一步使用滚动数组优化：

注意 c_i 可正可负，dp[i] 的初值应设为负无穷，dp[0]=0，部分代码如下：

// 初始化
for (int i = 1; i <= n; ++i) { dp[i]=-1e9; }
dp[0] = 0;

// D.P.
for (int i = 1; i <= n; ++i) {
    for (int j = B; j >= 0; --j) {
        int x = min(B, j+b[i]);
        dp[x]  = min(dp[x],dp[j]+c[i]);
    }
}

这种改写方法能保证正确性的同时保证数组开得下，时间复杂度 O(n \log (n^2))=O(n \log n)。

与最小生成树结合

例：POJ-2728，AC代码提交记录（P！O！J！你！*！*！）

与 spfa 判负环结合

例：洛谷P3199，AC代码提交记录