何為01分數規劃

01分數規劃解決的是這麼一類問題：

從給定的數列 a i 、 b i {a_i}、{b_i} ai、bi，求 ∑ i = 1 a i ∗ p i ∑ i = 1 b i ∗ p i \frac{\sum_{i=1}{a_i}*p_i}{\sum_{i=1}{b_i}*p_i} ∑i=1bi∗pi∑i=1ai∗pi的最值問題

其中p為一個01數列。

也就是從一個二進制組清單中選一些二進制組，求x項之和/y項和的最值。

常常是求最大中的最小、最小中的最大。

這類問題我們通常用二分+分數規劃來做

詳解

直接求解不容易，我們可以考慮如何判斷某個答案是否合法。

下面以最小值為例：

假設二分出答案ans

令 ∑ i = 1 a i ∗ p i ∑ i = 1 b i ∗ p i \frac{\sum_{i=1}{a_i}*p_i}{\sum_{i=1}{b_i}*p_i} ∑i=1bi∗pi∑i=1ai∗pi中分母為A，分子為B

那麼 = A / B > = a n s =A/B >= ans =A/B>=ans

= A > = a n s ∗ B =A>=ans*B =A>=ans∗B

= A − B ∗ a n s > = 0 =A-B*ans>=0 =A−B∗ans>=0

把AB兩個式子展開：

= ∑ i = 1 a i ∗ p i − b i ∗ p i ∗ a n s > = 0 =\sum_{i=1}^{a_i*p_i-b_i*p_i*ans}>=0 =∑i=1ai∗pi−bi∗pi∗ans>=0

是以當最後一個式子成立的時候答案ans合法。

我們有注意到ans越大越不好滿足，是以這個是有單調性的。

如果ans不行，那麼比ans大的都不能滿足；如果ans合法，那麼比ans小的都合法。

是以我們可以二分ans，然後判斷。