做分?jǐn)?shù)規(guī)劃這類題目很多人第一次看到題解里“二分答案 check”那一套總覺得像是憑空冒出來的思路。我自己最開始刷“算法提高16.01分?jǐn)?shù)規(guī)劃”這個(gè)專題時(shí)也是一臉懵一個(gè)求最優(yōu)比率的問題怎么就變成二分判定問題了后來又遇到一堆變種什么最優(yōu)比率生成樹、最優(yōu)比率環(huán)發(fā)現(xiàn)萬變不離其宗。這篇就按我個(gè)人從入門到實(shí)戰(zhàn)的路徑把這個(gè)專題完整拆開聊一遍把模型、原理、代碼和坑都擺出來。適合看這篇的人主要是正在刷算法提高專題、遇到分?jǐn)?shù)規(guī)劃卻無從下手的同學(xué)或者是想徹底搞懂“為什么能二分”而不是只背板子的參賽選手。內(nèi)容不涉及高深數(shù)學(xué)只要你有基礎(chǔ)的二分思想會(huì)寫最短路或者最小生成樹就能跟著走完整個(gè)過程。1. 先把分?jǐn)?shù)規(guī)劃的問題模型搞清楚1.1 從一道生活題說起我們經(jīng)常遇到這樣的問題有 n 個(gè)東西每個(gè)東西都有一個(gè)收益 a_i 和一個(gè)代價(jià) b_i現(xiàn)在要在這 n 個(gè)東西里選若干個(gè)使得選出來的東西總收益和總代價(jià)的比值最大。注意這里不是簡(jiǎn)單的總和最大而是兩個(gè)總和的比值最大。舉個(gè)最直觀的例子。你有幾門課的成績(jī)每門課有“學(xué)分”和“分?jǐn)?shù)”現(xiàn)在你可以放棄其中若干門課目標(biāo)是讓剩余課程的平均分最高。這時(shí)候每門課的 b_i 是學(xué)分a_i 是這門課的成績(jī)乘以學(xué)分。你放棄幾門分低的課平均分確實(shí)會(huì)上去但你得想想放棄課程會(huì)導(dǎo)致分母也變小所以“貪心地放棄最低分”并不一定最優(yōu)。這就是分?jǐn)?shù)規(guī)劃要處理的核心矛盾分子和分母同時(shí)隨選擇變化不能拆開看。再換一個(gè)大家熟悉的實(shí)際場(chǎng)景給你若干組數(shù)據(jù)每組有完成的工作量和消耗的時(shí)間你要選幾組使得“總工作量 / 總時(shí)間”最大。直接一個(gè)個(gè)比較“單位時(shí)間工作量”然后排序選最大的只有在能拆開按比例取的時(shí)候才成立一旦要求整體選擇這種貪心就會(huì)失效。1.2 從實(shí)際需求抽象出數(shù)學(xué)模型把所有選擇抽象一下假設(shè)我們有一個(gè)變量 x_i 表示“第 i 個(gè)元素是否被選中”取 0 或 1。那么我們要最大化的目標(biāo)就是最大化Σ(a_i * x_i) / Σ(b_i * x_i)其中 b_i 通常要求為正數(shù)。分母不能為 0所以至少得選一個(gè)元素。這類問題統(tǒng)稱分?jǐn)?shù)規(guī)劃又叫比率規(guī)劃。“16.01 分?jǐn)?shù)規(guī)劃”這個(gè)專題編號(hào)常見的命名方式其實(shí)指的就是這類問題。核心難點(diǎn)是目標(biāo)函數(shù)既不是線性的也不是凸的直接求導(dǎo)、直接動(dòng)態(tài)規(guī)劃都不太好辦。但它的特殊之處在于我們關(guān)心的不是每一項(xiàng)的比值而是整體加和之后的比率。關(guān)鍵轉(zhuǎn)化來了。假設(shè)我們猜測(cè)最終最優(yōu)值是 r也就是說存在一種選擇方案讓分子和分母的比值 ≥ r那么這個(gè)條件等價(jià)于Σ(a_i * x_i) - r * Σ(b_i * x_i) ≥ 0把它改寫一下Σ((a_i - r * b_i) * x_i) ≥ 0看到?jīng)]右邊變成了一個(gè)關(guān)于 x_i 的線性求和式。每一項(xiàng)的“價(jià)值”變成了 (a_i - r * b_i)。如果我們要判斷是否存在一個(gè)選法讓這個(gè)式子大于等于 0那就變成了一個(gè)非常普通的問題從一堆物品中按照某個(gè)規(guī)則挑選若干物品使得選中物品的“新價(jià)值”之和最大再看這個(gè)最大值是否非負(fù)。這個(gè)變換是整個(gè)分?jǐn)?shù)規(guī)劃專題的靈魂。1.3 分?jǐn)?shù)規(guī)劃常見的三種形式在算法題里分?jǐn)?shù)規(guī)劃很少單獨(dú)出現(xiàn)通常是作為“外殼”套在別的經(jīng)典算法外面。我按自己刷題遇到的頻率整理一下。第一種是最基礎(chǔ)的 01 分?jǐn)?shù)規(guī)劃也就是上面那種“選若干物品最大化比率”。典型解法是二分 r然后根據(jù)新價(jià)值是否大于 0 判斷。判斷的時(shí)候往往還要加一個(gè)約束比如“恰好選 k 個(gè)”“至少選 k 個(gè)”“最多選 k 個(gè)”那就對(duì)應(yīng)不同的子問題比如排序取前 k 個(gè)、背包 DP 等。第二種是最優(yōu)比率生成樹。題目給你一張圖每條邊有兩個(gè)權(quán)值比如“成本”和“收益”要你找一棵生成樹讓這棵樹的“總收益 / 總成本”最大。二分 r 之后每條邊的權(quán)值變成 a_i - r * b_i判斷是否存在生成樹使得總權(quán)值 ≥ 0。這時(shí)候套的就是最小生成樹算法只是邊權(quán)被重新定義了。第三種是最優(yōu)比率環(huán)。這個(gè)稍微繞一點(diǎn)給一個(gè)有向圖每條邊有權(quán)值 a_i 和 b_i要找一個(gè)環(huán)使得環(huán)上所有邊的“總收益 / 總代價(jià)”最大。二分 r 之后每條邊的權(quán)值變成 a_i - r * b_i要找是否存在一個(gè)正環(huán)。正環(huán)判斷一般用 SPFA 的某個(gè)變種這也是很多人覺得難的地方。無論是哪一種核心都逃不過那個(gè)關(guān)鍵變換把“比值 ≥ r”變成“線性值 ≥ 0”然后用已知算法去判定。這也是為什么我建議先把第一種吃透后面兩種就是套殼。2. 二分法為什么“猜答案”可行2.1 二分的是答案不是選擇方案很多人看到“二分答案”四個(gè)字第一反應(yīng)是我們不是要找最優(yōu)的選擇方案嗎怎么變成猜一個(gè)數(shù)了這里的關(guān)鍵在于分?jǐn)?shù)規(guī)劃最優(yōu)值的范圍通常比較容易確定而且判斷“當(dāng)前猜的值是否可行”是相對(duì)容易的。我們并不需要直接構(gòu)造出最優(yōu)方案而是通過不斷收縮答案區(qū)間逼近那個(gè)最優(yōu)比率。假設(shè)我們猜了一個(gè)值 r然后對(duì)所有元素計(jì)算差值 c_i a_i - r * b_i。如果存在一個(gè)可行選擇方案使得中選元素的 c_i 之和大于等于 0那么說明最優(yōu)值至少是 r也就是答案在 [r, 上界] 區(qū)間里如果無論怎么選這個(gè)和都小于 0說明我們想要的比率根本達(dá)不到 r答案應(yīng)該比 r 小。之所以可以二分是因?yàn)檫@個(gè)判定結(jié)果關(guān)于 r 是單調(diào)的。r 越小c_i a_i - r * b_i 越大顯然越容易滿足“之和 ≥ 0”r 越大c_i 越小越不容易滿足。所以存在一個(gè)臨界點(diǎn)低于它答案可行高于它不可行這個(gè)臨界點(diǎn)就是最優(yōu)比值。這個(gè)單調(diào)性非常重要。它不是“看起來像”單調(diào)而是嚴(yán)格單調(diào)因?yàn)?b_i 都是正的r 增大時(shí)每一項(xiàng) c_i 都嚴(yán)格減少或者至少不增總和也嚴(yán)格減少所以一旦某個(gè) r 可行那么任何比它小的 r 也一定可行。這就保證了二分完全正確。2.2 判定問題的具體化現(xiàn)在問題聚焦到了給定 r 和所有 c_i如何判斷是否存在合法選法讓所選元素的 c_i 之和 ≥ 0。如果是 01 分?jǐn)?shù)規(guī)劃“選任意多個(gè)”那我們直接看所有 c_i 中正數(shù)的和是否 ≥ 0 就行因?yàn)槿钦龜?shù)的都選上肯定最優(yōu)負(fù)數(shù)的都不選。如果要求“恰好選 k 個(gè)”那就是選出 c_i 最大的 k 個(gè)看前 k 大之和是否大于等于 0。這里要注意排序選前 k 大之所以能成立是因?yàn)榕袛鄺l件里沒有其他相互依賴的約束。一旦加上“必須選滿 n 個(gè)中的某部分”“分組一定要達(dá)到某條件”那就可能要用背包 DP 或者網(wǎng)絡(luò)流來判定。很多分?jǐn)?shù)規(guī)劃題目的難點(diǎn)其實(shí)在這里分?jǐn)?shù)規(guī)劃本身只提供了外層框架。我自己做題的習(xí)慣是先把判定子問題抽象出來明確要套用什么算法。比如選 k 個(gè)最大值排序選一個(gè)生成樹最小生成樹選一個(gè)環(huán)SPFA 判正環(huán)選若干物品且容量有限背包 DP只要判定算法是多項(xiàng)式復(fù)雜度外面的二分次數(shù)一般是 50 到 60 次整體復(fù)雜度基本可控。2.3 check 函數(shù)的編寫要點(diǎn)編寫二分判定函數(shù)時(shí)有一個(gè)細(xì)節(jié)非常重要c_i 的浮點(diǎn)誤差。由于 a_i 和 b_i 可能是很大的整數(shù)r 是浮點(diǎn)數(shù)計(jì)算 c_i a_i - r * b_i 時(shí)要注意精度損失。更穩(wěn)妥的做法是使用更高精度的浮點(diǎn)數(shù)或者在特殊情況下把比較轉(zhuǎn)化為整數(shù)運(yùn)算。舉個(gè)例子假設(shè) a_i 和 b_i 都是整數(shù)我們要判斷“前 k 個(gè) c_i 之和是否 ≥ 0”。如果直接用浮點(diǎn)數(shù)累加最終和特別接近 0 時(shí)可能因?yàn)檎`差導(dǎo)致判錯(cuò)。這時(shí)候可以把不等式左右都乘以一個(gè)數(shù)或者干脆在累加時(shí)用 long double等排序完后再和 0 比較。另一個(gè)重點(diǎn)是二分的邊界。最優(yōu)比率不會(huì)超過 max(a_i / b_i)所以二分上界可以取這個(gè)最大值下界取 0。也有人為了省事直接取一個(gè)很大的數(shù)比如 1e12但這樣會(huì)白白多算幾次二分。我建議還是老老實(shí)實(shí)求一個(gè)合理的上界一方面減少迭代次數(shù)另一方面防止浮點(diǎn)數(shù)在極大值附近丟失精度。二分次數(shù)怎么定也很關(guān)鍵。很多人用 while (r - l eps) 來判斷但這樣容易因?yàn)?eps 設(shè)得不對(duì)而無限循環(huán)。我推薦直接固定循環(huán) 60 次或者 80 次每次把區(qū)間縮小一半。這樣不用糾結(jié) eps 該設(shè)多少也能保證精度足夠。原因很簡(jiǎn)單double 的有效位數(shù)有限固定迭代次數(shù)比固定差值更可控。3. 經(jīng)典例題實(shí)操考試放棄題3.1 題目設(shè)計(jì)與建模過程為了把上面的思路落下來我們用一個(gè)經(jīng)典題目走一遍完整流程。假設(shè)有 n 門考試第 i 門考試的總分是 b_i你得了 a_i 分?，F(xiàn)在學(xué)校允許你放棄其中 k 門課問剩余課程的平均分最高可以是多少。平均分的定義是剩余課程得分之和 / 剩余課程滿分之和。注意不是把每門課單獨(dú)算百分制再取平均而是加權(quán)平均權(quán)重就是每門課的滿分。這一點(diǎn)很關(guān)鍵很多人一開始會(huì)理解錯(cuò)。建模過程是這樣的每門課其實(shí)是一個(gè)物品b_i 是滿分a_i 是得分。我們要從 n 個(gè)物品中去掉 k 個(gè)相當(dāng)于選擇剩余的 n-k 個(gè)物品讓 Σa_i / Σb_i 最大。這里“選多少個(gè)”是固定的所以到了二分判定環(huán)節(jié)我們會(huì)計(jì)算所有 c_i a_i - r * b_i然后排序取最大的 n-k 個(gè)看它們的和是否 ≥ 0。細(xì)想一下為什么要取最大而不是最小因?yàn)槲覀円袛唷笆欠翊嬖谝环N選法讓所選物品的 c_i 之和 ≥ 0”在選固定數(shù)量 m 個(gè)物品時(shí)肯定選 c_i 最大的 m 個(gè)最有利。如果這 m 個(gè)最大的加起來都小于 0那其他任何選法更不可能滿足條件。這個(gè)邏輯非常直接。3.2 完整代碼實(shí)現(xiàn)我直接用 C 寫一版完整實(shí)現(xiàn)思路就是二分套排序判定。假設(shè)輸入 n 和 k然后兩個(gè)數(shù)組 a 和 b最后輸出最大平均分。#include bits/stdc.h using namespace std; const int MAXN 1005; int n, k; double a[MAXN], b[MAXN]; double c[MAXN]; bool check(double r) { for (int i 0; i n; i) { c[i] a[i] - r * b[i]; } sort(c, c n, greaterdouble()); double sum 0; int m n - k; for (int i 0; i m; i) { sum c[i]; } return sum 0; } int main() { while (scanf(%d%d, n, k) 2) { if (n 0 k 0) break; for (int i 0; i n; i) scanf(%lf, a[i]); for (int i 0; i n; i) scanf(%lf, b[i]); double l 0, r 0; for (int i 0; i n; i) { r max(r, a[i] / b[i]); } for (int iter 0; iter 60; iter) { double mid (l r) / 2; if (check(mid)) { l mid; } else { r mid; } } printf(%.6lf\n, l); } return 0; }這段代碼是一個(gè)完整可運(yùn)行的程序核心就是 check 函數(shù)。我故意把 a 和 b 聲明為 double是為了讓代碼簡(jiǎn)潔但如果輸入是整數(shù)改成 long long 讀入、在 check 內(nèi)部轉(zhuǎn)成 double 計(jì)算會(huì)更好避免大整數(shù)在浮點(diǎn)數(shù)轉(zhuǎn)換時(shí)出現(xiàn)意外誤差。輸出的精度也要注意。二分 60 次之后區(qū)間長(zhǎng)度大約是初始區(qū)間長(zhǎng)度除以 2 的 60 次方早就超過 double 的精度極限了。所以輸出 l 或者 r 都可以但保留 6 位小數(shù)是最常見的做法。有些題目要求百分比輸出或者保留 3 位小數(shù)那就按照題目要求來。3.3 復(fù)雜度與精度分析這個(gè)解法的時(shí)間復(fù)雜度分兩塊。一塊是外層二分固定 60 次。一塊是每次 check 里的排序復(fù)雜度 O(n log n)。所以總復(fù)雜度是 O(60 * n log n)n 到 1e5 的時(shí)候大概能跑進(jìn)一兩秒n 到 1e6 就有點(diǎn)懸了。如果題目 n 特別大但恰好不需要排序而是用 nth_element 只取前 m 個(gè)就可以把 check 降成 O(n)。我提供的是排序版本因?yàn)橥ㄓ眯院涂勺x性更好實(shí)際比賽里如果 T 組數(shù)據(jù)且 n 巨大我會(huì)改成 nth_element 優(yōu)化。關(guān)于精度有一個(gè)實(shí)用性建議如果 a_i 和 b_i 都是整數(shù)而且題目要求輸出百分?jǐn)?shù)也就是把平均分乘以 100那么在 check 里可以直接比較a[i] * 100 - r * b[i] 0這樣 r 表示的是“百分制平均分”避免最后輸出的時(shí)候還要再乘一次導(dǎo)致二次誤差。我見過不少同學(xué)二分時(shí)用的是原始分?jǐn)?shù)輸出時(shí)才乘 100結(jié)果因?yàn)楦↑c(diǎn)誤差差了 0.01 被卡。這種細(xì)節(jié)最冤枉寫代碼時(shí)提前想清楚單位能省很多事。4. Dinkelbach 算法另一種迭代思路4.1 用最優(yōu)解不斷逼近最優(yōu)值除了二分分?jǐn)?shù)規(guī)劃還有一個(gè)經(jīng)典迭代算法叫 Dinkelbach 算法。它的思路更像是在“用上一次的最優(yōu)方案來修正當(dāng)前的候選答案”。具體來說我們從一個(gè)初始猜測(cè)值 r 開始。在當(dāng)前 r 下找到使得 Σ(a_i - r * b_i) 最大的選擇方案假設(shè)這個(gè)最大和是 F(r)。如果 F(r) ≥ 0我們可以把 r 更新為“當(dāng)前最優(yōu)選法”的實(shí)際比率即r_new Σa_i / Σb_i 這里的選法是剛才求出的最優(yōu)選法然后重復(fù)這個(gè)過程直到 r 的變化小到可以忽略。為什么有效因?yàn)槊看胃潞蟮?r_new 一定是比之前更優(yōu)的下界而且每次選法對(duì)應(yīng)的實(shí)際比率會(huì)單調(diào)遞增。這個(gè)算法的收斂速度通常比二分快尤其在后半段往往幾次迭代就能達(dá)到很高精度。4.2 實(shí)際對(duì)比何時(shí)選二分何時(shí)選 Dinkelbach從編碼角度講二分更直觀不容易寫錯(cuò)Dinkelbach 則需要你額外保存“當(dāng)前最優(yōu)方案所選元素”的和代碼量稍微多一點(diǎn)而且要求判定問題本身能方便地求出最優(yōu)方案而不只是判定可行性。從效率角度講Dinkelbach 的迭代次數(shù)在多數(shù)情況下遠(yuǎn)小于 60 次可能十幾二十次就收斂了。但它的每輪迭代同樣要跑排序或者最短路所以實(shí)際差別不是特別大。不過有一點(diǎn)Dinkelbach 適合那些 check 過程本身就能返回最優(yōu)選擇方案的場(chǎng)景如果判定算法只能返回一個(gè) bool那還是用二分省事。我個(gè)人的習(xí)慣是比賽時(shí)默認(rèn)寫二分因?yàn)闀r(shí)間復(fù)雜度可控、魯棒性強(qiáng)只有在 T 組數(shù)據(jù)特別多、二分次數(shù)明顯成為瓶頸時(shí)才改用 Dinkelbach。還有一種情況就是判定問題本身用的是 SPFA 判正環(huán)這類復(fù)雜算法每多一次迭代都心驚膽戰(zhàn)這時(shí)候 Dinkelbach 的快速收斂?jī)?yōu)勢(shì)就很明顯了。需要注意Dinkelbach 對(duì)初值有一定依賴。如果初值設(shè)得太離譜第一輪迭代可能導(dǎo)致更新出很奇怪的結(jié)果。我的做法是取所有 a_i / b_i 的最大值作為初值反正這個(gè)值必然不小于最終答案迭代起來很快。5. 分?jǐn)?shù)規(guī)劃的變種問題拓展5.1 最優(yōu)比率生成樹的二分判定前面提到最優(yōu)比率生成樹也是同一套路?，F(xiàn)在假設(shè)每條邊有兩個(gè)屬性 cost 和 value要選 n-1 條邊形成生成樹讓 value 之和與 cost 之和的比值最大。在二分到 r 時(shí)每條邊的新權(quán)值是 value_i - r * cost_i。我們需要判斷是否存在一棵生成樹讓總權(quán)值 ≥ 0。注意這里不是求最小生成樹隨便判斷一下而是要判斷“最大可能的生成樹權(quán)值”是否非負(fù)。用最小生成樹算法求出來的其實(shí)是最小權(quán)值如果最小權(quán)值都 ≥ 0那所有生成樹都 ≥ 0但我們要判斷的是是否存在某一棵 ≥ 0所以應(yīng)該求最大生成樹。這個(gè)問題我踩過坑用 Kruskal 時(shí)習(xí)慣性按邊權(quán)從小到大排序結(jié)果一直錯(cuò)。最優(yōu)比率生成樹應(yīng)該按新邊權(quán)從大到小排序找最大生成樹看總權(quán)值是否 ≥ 0。這里的“最大”不是指收益最大而是指在當(dāng)前 r 下新權(quán)值之和最大這樣才能最大化滿足條件的機(jī)會(huì)。復(fù)雜度方面二分 60 次每次 Kruskal 是 O(m log m)m 是邊數(shù)。如果邊數(shù)到 2e5總復(fù)雜度就是 60 * 2e5 * log通常情況下可以接受但要注意常數(shù)。我試過在一些 OJ 上用 Kruskal 套分?jǐn)?shù)規(guī)劃如果不加優(yōu)化很容易超時(shí)?？梢蕴崆鞍堰叞丛?cost 排序減少每次重排的工作不過新權(quán)值依賴 r嚴(yán)格來說沒法完全復(fù)用排序結(jié)果只能盡量?jī)?yōu)化常數(shù)。5.2 最優(yōu)比率環(huán)與正環(huán)判定最優(yōu)比率環(huán)是另一個(gè)常見變種也是我個(gè)人覺得最容易繞暈的。給定有向圖每條邊有收益 w_i 和花費(fèi) t_i找一個(gè)有向環(huán)讓環(huán)上總收益 / 總花費(fèi)最大。二分 r 后每條邊的新權(quán)值是 w_i - r * t_i我們要判斷是否存在一個(gè)環(huán)使得環(huán)上所有邊的新權(quán)值之和 ≥ 0。換句話說判斷圖中是否存在正權(quán)環(huán)。正權(quán)環(huán)的判定有兩種常見做法。一種是把權(quán)值取反然后判負(fù)環(huán)用 SPFA 的標(biāo)準(zhǔn)寫法另一種是直接用最長(zhǎng)路加入隊(duì)次數(shù)判正環(huán)。我推薦第一種因?yàn)榕胸?fù)環(huán)的 SPFA 模板更常見不易寫錯(cuò)。具體實(shí)現(xiàn)時(shí)注意初始化判負(fù)環(huán)要初始化為 INF判正環(huán)要初始化為 0 或 -INF入隊(duì)次數(shù)超過 n 說明存在環(huán)。這里有個(gè)細(xì)節(jié)如果圖本身不連通要多次從不同起點(diǎn)跑 SPFA或者建一個(gè)超級(jí)源點(diǎn)連向所有點(diǎn)否則會(huì)漏判。最優(yōu)比率環(huán)還有一個(gè)坑二分時(shí) r 的初始上界不能用簡(jiǎn)單的 max(w_i/t_i) 來算因?yàn)榄h(huán)是整體加和單條邊的比率不能代表整個(gè)環(huán)的比率。我的做法是設(shè)一個(gè)較大的上界比如 1e7或者根據(jù)題目數(shù)據(jù)范圍算一個(gè)保底值。反正 SPFA 判定本身不慢多幾次二分問題不大。5.3 分?jǐn)?shù)規(guī)劃與背包 DP 的組合還有一種變種比較少見但很有代表性選出的物品數(shù)量不固定但受到某個(gè)總?cè)萘肯拗?。比如每個(gè)物品有體積背包容量是 V要從物品中選一個(gè)子集讓總收益 / 總花費(fèi)最大。這種問題在二分到 r 后判定就變成了一個(gè) 0/1 背包問題每個(gè)物品價(jià)值是 w_i - r * c_i要求在體積不超過 V 的前提下最大化所選物品的價(jià)值之和再看這個(gè)最大值是否 ≥ 0。這里的復(fù)雜度就和前面的排序題明顯不同了。背包 DP 的復(fù)雜度是 O(n * V)外面再乘 60 次二分必須注意 V 的大小。如果 V 到 1e5、n 到 100整體勉強(qiáng)能過如果 V 到 1e6那就得考慮優(yōu)化比如可行性背包轉(zhuǎn)成完全背包等。但不管怎樣框架還是一樣的二分 r然后套背包判定。從這些變種可以看出分?jǐn)?shù)規(guī)劃本身并不難難的是掛在它下面的那層“判定算法”。所以我的建議是先確保自己對(duì)排序、最小生成樹、SPFA、背包 DP 這些基礎(chǔ)算法非常熟練再來攻克分?jǐn)?shù)規(guī)劃專題會(huì)順暢很多。我最初就是基礎(chǔ)算法不牢結(jié)果在判定環(huán)節(jié)反復(fù)出錯(cuò)還以為是分?jǐn)?shù)規(guī)劃本身理解錯(cuò)了。6. 常見問題與避坑技巧實(shí)錄6.1 二分邊界設(shè)錯(cuò)導(dǎo)致答案偏移我見過很多初學(xué)者把二分上界直接設(shè)成一個(gè)很大的常數(shù)比如 1e9然后循環(huán) 50 次發(fā)現(xiàn)答案偏大或者偏小。原因在于浮點(diǎn)數(shù)在非常大和非常小之間二分時(shí)后半段可能已經(jīng)達(dá)到了浮點(diǎn)精度極限繼續(xù)二分只是在一個(gè)區(qū)間內(nèi)抖動(dòng)不會(huì)繼續(xù)收斂。正確做法是先掃描一遍所有元素求出 a_i / b_i 的最大值作為 r 的上界。這個(gè)值一定不小于最終答案因?yàn)閱为?dú)選某個(gè)物品的比率不可能超過所有物品中的最大比率整體比率也不會(huì)超過它。數(shù)學(xué)上很好理解分子的加權(quán)平均除以分母的加權(quán)平均不可能大于各個(gè)分子分母比值的最大值這是加權(quán)平均的基本性質(zhì)。6.2 排序方向搞反這個(gè)錯(cuò)誤特別隱蔽。在“去掉 k 個(gè)物品”的題目里我們要選最大的 n-k 個(gè) c_i 值在“生成樹”里我們要找最大生成樹在“環(huán)”里我們要找正環(huán)?？雌饋矶际恰白畲蟆钡@和很多人寫慣了的“最小生成樹”“最短路徑”套路不一樣容易習(xí)慣性搞反。我自己有一次寫最優(yōu)比率環(huán)SPFA 判的是負(fù)環(huán)結(jié)果一直以為代碼寫錯(cuò)折騰了半天才發(fā)現(xiàn)是判環(huán)方向反了。后來我給自己定了一條規(guī)則分?jǐn)?shù)規(guī)劃的所有判定先想清楚“我要不要最大化這個(gè)新權(quán)值的和”然后順著目標(biāo)選算法。最大化用最長(zhǎng)路、最大生成樹最小化用最短路、最小生成樹分清之后再動(dòng)手寫代碼。6.3 精度比較時(shí)使用 eps 不當(dāng)判斷 sum 0 時(shí)有人喜歡寫 sum -eps認(rèn)為這樣更寬容有人寫 sum eps認(rèn)為這樣更嚴(yán)格。這個(gè)選擇其實(shí)取決于你二分后輸出的目標(biāo)是最大值還是最小值以及你二分循環(huán)的條件。我的建議是如果使用固定迭代次數(shù)二分check 里直接和 0 比較就行不需要 eps。因?yàn)槎盅h(huán)結(jié)束時(shí)答案的誤差已經(jīng)由迭代次數(shù)保證了check 里的微小偏差不會(huì)影響最終輸出的位數(shù)。如果你非要用 while (r - l eps)那 eps 至少要設(shè)在 1e-8 以下并且配合 long double 使用否則容易死循環(huán)或者結(jié)果差一位。6.4 輸出格式要求是百分?jǐn)?shù)還是小數(shù)很多分?jǐn)?shù)規(guī)劃題目要求輸出百分?jǐn)?shù)比如保留三位小數(shù)加一個(gè)百分號(hào)。你在二分時(shí)的 r 是原始比率輸出前要乘以 100這時(shí)候可能出現(xiàn) 0.001 的精度問題。我建議在輸入后直接把 a_i 或 b_i 按要求縮放。如果輸出百分?jǐn)?shù)且保留三位小數(shù)可以在 check 里把 r 當(dāng)作百分?jǐn)?shù)來算這樣代碼里處理的單位與輸出單位一致減少一次換算誤差。這個(gè)方法雖然聽起來只是小技巧但真的能救你于卡精度之中。6.5 大數(shù)據(jù)讀取與常數(shù)優(yōu)化分?jǐn)?shù)規(guī)劃結(jié)合排序的版本主要瓶頸在排序上。如果 n 達(dá)到 1e6每次 check 都完整排序會(huì)非常吃力。一個(gè)常用優(yōu)化是改用 nth_element 只取第 k 大并同時(shí)求前 k 大之和這樣復(fù)雜度從 O(n log n) 降到 O(n)。還有一個(gè)小技巧對(duì)于“選前 m 個(gè)最大值之和”不需要把所有 c_i 都存下來再排可以在生成 c_i 時(shí)同時(shí)維護(hù)一個(gè)大小為 m 的最小堆堆內(nèi)元素就是當(dāng)前最大的 m 個(gè)。這樣空間復(fù)雜度可能更高但思路一樣。具體用哪種取決于你更在乎代碼簡(jiǎn)潔性還是極限性能。6.6 多組數(shù)據(jù)時(shí)注意二分重置這個(gè)看起來是基礎(chǔ)問題但真的很常見。多組輸入時(shí)上界 r 和數(shù)組內(nèi)容都要重新初始化。我見過一個(gè)同學(xué)因?yàn)樯辖鐩]有重置第一組數(shù)據(jù)算出一個(gè)很大的上界第二組數(shù)據(jù)小一點(diǎn)二分直接從錯(cuò)誤范圍開始結(jié)果答案完全不對(duì)。我的習(xí)慣是每組數(shù)據(jù)進(jìn)來后除了讀入數(shù)組還要把 r 初始化為 0然后再做掃描求最大值。這個(gè)操作雖然不起眼但能避免一個(gè)很惡心的排查過程。7. 一點(diǎn)個(gè)人經(jīng)驗(yàn)分享分?jǐn)?shù)規(guī)劃這個(gè)專題最難的不是那套二分框架而是你能不能識(shí)別出題目背后的比率結(jié)構(gòu)。很多時(shí)候題目會(huì)把“收益”和“代價(jià)”隱藏起來。比如“每位應(yīng)聘者有工作能力和期望薪資選若干人讓總能力 / 總薪資最大”本質(zhì)就是 01 分?jǐn)?shù)規(guī)劃。多練幾道題之后你會(huì)逐漸形成一種直覺只要看到“比率”“平均”“單位成本收益”這些詞就該往分?jǐn)?shù)規(guī)劃上想。如果一定要說一個(gè)最重要的技巧那就是把所有問題都轉(zhuǎn)化到“判斷是否存在選法使新權(quán)值之和非負(fù)”這一層。之后無論面對(duì)生成樹、環(huán)還是背包變種思路都會(huì)特別清晰。做專題訓(xùn)練時(shí)不要急著看題解先自己想清楚如果二分一個(gè)數(shù)check 函數(shù)里該做什么這個(gè)問題的答案往往是解題的核心。最后說個(gè)實(shí)踐建議把經(jīng)典題目換著寫法做一遍。同一道 01 分?jǐn)?shù)規(guī)劃先用二分寫一遍再用 Dinkelbach 寫一遍然后在相同數(shù)據(jù)下對(duì)比兩者的輸出和運(yùn)行時(shí)間。這個(gè)對(duì)比做完你對(duì)該算法的理解絕對(duì)比看十篇題解都深刻。