01 分数规划

引入

其主要为了解决下面的问题：

[!question] 问题引入

现在存在 \(n\) 个 bool 变量 \(w_i\) ，然后此时需要让：

\[ \frac{\sum_{i=1}^n w_i \cdot a_i}{\sum_{i=1}^n w_i \cdot b_i} \]

最大，保证所有 \(a_i, b_i > 0\) 。

主题思想

对于这个东西我们考虑进行二分答案，假设当前正在验证 \(mid\) ，因此相当于需要满足：

\[ \frac{\sum_{i=1}^n w_i \cdot a_i}{\sum_{i=1}^n w_i \cdot b_i} \ge mid \]

因此我们考虑把等式左边乘到右边，因此可以得到：

\[ \sum_{i=1}^n w_i \cdot a_i - \left(\sum_{i=1}^n w_i \cdot b_i\right) \times mid \ge 0 \]

\[ \sum_{i=1}^n w_i (a_i - mid \cdot b_i) \ge 0 \]

（注意一下 \(w\) 不能一个都不选）

然后此时这个式子就可以贪心做了，为了防止上面情况的发生，一般的题目都会有一个其他的要求，比如 \(w_i = 1\) 必须有至少 \(k\) 个，这里直接贪心就可以了。

应用

一般题目不会有特别明显的分数特征，而是需要经过变化，比如下面这个题：

[!note] P5319 [BJOI2019] 奥术神杖

首先重点是这个贡献，观察到如果匹配的字符串越多， \(val\) 的乘积越多，但是同时···

我们考虑对于式子加上一个 \(\ln\) ，于是现在就变成了 \(\frac{1}{m} \sum \ln{m}\)

然后这里就变成 01 分数规划形式了，直接二分并且再 AC 自动机上 DP 就可以了。