問題模型1

基本01分數(shù)規(guī)劃問題

給定n$n$個二元組(valuei,costi)$(value_i,cost_i)$，valuei$value_i$是選擇此二元組獲得的價值（非負），costi$cost_i$是選擇此二元組付出的代價（非負），設(shè)xi(xi∈{0,1})$x_i(x_i/in /{0,1/})$代表第i$i$個二元組的選與不選，最大(小)化下式 maximize(or minimize)   r=∑valuei?xi∑costi?xi $$maximize(or/ minimize)/ / / r = /frac{/sum value_i /cdot x_i}{/sum cost_i/cdot x_i}$$

解決方法

二分法

設(shè)r$r$最大值為r?$r^*$， r?=∑valuei?xi∑costi?xi $$r^* = /frac{/sum value_i /cdot x_i}{/sum cost_i/cdot x_i}$$

∑valuei?xi?r??∑costi?xi=0 $$/sum value_i /cdot x_i - r^*/cdot /sum cost_i/cdot x_i = 0$$

設(shè)一個函數(shù)，自變量為r$r$值， f(r)=∑valuei?xi?r??∑costi?xi $$f(r) =/sum value_i /cdot x_i - r^*/cdot /sum cost_i/cdot x_i$$

觀察這個函數(shù)，假如{xi}$/{x_i/}$固定，則這個函數(shù)就是坐標系中一條直線(y=B?A?x$y = B - A/cdot x$)，每一組{xi}$/{x_i/}$對應(yīng)著一條直線，這些直線斜率非正(因為?A=?∑costi?xi≤0$-A =- /sum cost_i/cdot x_i /le 0$)，縱截距非負(因為B=∑valuei?xi≥0$B =/sum value_i /cdot x_i /ge 0$ )，如圖1。 對于每一條直線，當f(r)=0$f(r)=0$時，橫截距就是這一組的r$r$，那么r?$r^*$就是每條直線橫截距的最大值（每組{xi}$/{x_i/}$對應(yīng)r$r$的最大值）如圖2。 在圖中上任取一條垂直x$x$軸的豎線， 如果存在直線與這條豎線的交點縱坐標為正，那么最優(yōu)值一定在當前豎線的右側(cè)； 如果所有直線與這條豎線交點縱坐標為負，那么最優(yōu)值一定在當前豎線的左側(cè)； 如果所有直線與這條豎線交點縱坐標非正且存在直線與這條豎線交點縱坐標為0，那么當前豎線橫坐標即為最優(yōu)值r?$r^*$。 按照這個思想，可以二分答案r$r$，那么二分時如何進行判斷呢？

選擇一個r$r$時需要判斷所有f(r)$f(r)$的最大值是否為0，如果max{f(r)}>0$max/{f(r)/} > 0$則r<r?$r < r^*$；如果max{f(r)}<0$max/{f(r)/} < 0$ 則 r>r?$r > r*$。 怎樣求max{f(r)}$max/{f(r)/}$? f(r)=∑valuei?xi?r?∑costi?xi=∑(valuei?r?costi)?xi $$/begin{aligned}f(r) &= /sum value_i /cdot x_i - r /cdot /sum cost_i/cdot x_i // &= /sum (value_i-r/cdot cost_i) /cdot x_i/end{aligned}$$

二分一個r$r$時，每個二元組的valuei?r?costi$value_i-r/cdot cost_i$ 都可以求出，設(shè)其為weighti$weight_i$，現(xiàn)在的目標就是找到一組{xi}$/{x_i/}$使得∑wighti?xi$/sum wight_i/cdot x_i$最大（即求max{f(r)}$max/{f(r)/}$）。怎么找到這一組{xi}$/{x_i/}$，或者直接求得max{f(r)}$max/{f(r)/}$呢？具體問題具體分析，經(jīng)常借助最短路算法判斷是否存在負環(huán)。下面會有幾道例題。

01分數(shù)規(guī)劃還會與其他問題結(jié)合，如網(wǎng)絡(luò)流等。

Dinkelbach$Dinkelbach$算法

這個算法我是在寫這篇文章時才知道的。

思考上述二分算法的思路，設(shè)二分過程中某一個二分值為r$r$，二分時的判斷條件是max{f(r)}$max/{f(r)/}$的正負性，而這個r$r$除了讓L$L$右移或者R$R$左移就沒有用了。現(xiàn)在思考某一過程中r$r$與max{f(r)}$max/{f(r)/}$能否再被利用。 二分時，假如max{f(r)}>0$max/{f(r)/}>0$這說明最優(yōu)解在當前r$r$的右側(cè)，于是讓L=r$L=r$，但是，如果將L$L$移動到max{f(r)}$max/{f(r)/}$對應(yīng)直線的橫截距呢？顯然，算法會變得更快。這個思想就是Dinkelbach$Dinkelbach$算法的內(nèi)涵。 Dinkelbach$Dinkelbach$實質(zhì)上是一種迭代算法，基于這樣的思想：不去二分答案，而是先隨便給定一個答案，然后根據(jù)更優(yōu)的解（max{f(r)}$max/{f(r)/}$對應(yīng)直線的橫截距）不斷移動答案，逼近最優(yōu)解。理論上它比二分快些。 在這個算法中，一般將r$r$初始化為0$0$。

兩種算法的比較

Dinkelbach$Dinkelbach$算法的弊端就是需要保存解。這兩個算法解決統(tǒng)一問題實際上都有可能快些。 我覺著我一般還是用二分。。。。

例題

只先寫了文章，還差相關(guān)題目的分析，代碼等。得等個一兩天再。2017-02-06留。

Poj2976Dropping tests

問題模型2

最優(yōu)比率生成樹

帶權(quán)無向圖G$G$， 對于圖中每條邊ei$e_i$， 都有valuei$value_i$和costi$cost_i$，現(xiàn)在求一棵生成樹T$T$，最大（小）化∑valuei∑costi,ei∈T$/frac{/sum value_i}{/sum cost_i},e_i/in T$

解決方法

套用01分數(shù)規(guī)劃模型，如果ei∈T$e_i/in T$則xi=1$x_i=1$否則xi=0$x_i=0$。

二分法

二分答案r$r$，邊賦值weighti=valuei?r?costi$weight_i = value_i-r/cdot cost_i$，因為是生成樹，邊的數(shù)量確定，那么max{f(r)}$max/{f(r)/}$需要選取前|G|?1$|G|-1$大的weighti$weight_i$，也就是求最大生成樹，按最大生成樹權(quán)值的正負性就可以二分了。

Dinkelbach$Dinkelbach$算法

當前答案r$r$，邊賦值weighti=valuei?r?costi$weight_i = value_i-r/cdot cost_i$，同樣求最大生成樹，找到max{f(r)}$max /{f(r)/}$對應(yīng)的邊集{xi}$/{x_i/}$，也就是最大生成樹的邊集。對這個邊集找橫截距當做下一次答案。橫截距是啥呢？ f(r)=B?A?rrr=0=B/A=∑valuei?xi∑costi?xi $$/begin{aligned}f(r)=B-A/cdot r &= 0 // r&=B/A //r &=/frac{/sum value_i /cdot x_i}{ /sum cost_i/cdot x_i} /end{aligned}$$

例題

poj2728Desert King(最優(yōu)比率生成樹)

問題模型3

最優(yōu)比率環(huán)

給定有點權(quán)和邊權(quán)的圖，求一個環(huán)，使得環(huán)的點權(quán)和與邊權(quán)和的比值最大。

解決方法

套用01分數(shù)規(guī)劃模型，點權(quán)為valuei$value_i$，邊權(quán)為costi$cost_i$，一個環(huán)為C$C$ 問題要求最大化∑valuei∑costi,(i∈C)$/frac{/sum value_i }{/sum cost_i},(i/in C)$ 邊數(shù)和點數(shù)是相同的，但上述式子表述不是很正確，意會即可。 若答案為r?$r^*$，那么任意一個環(huán) ∑valuei∑costi∑valueir??∑costi?∑valuei≤r?≤r??∑costi≥0 $$/begin{aligned}/frac{/sum value_i }{/sum cost_i}&/le r^* ///sum value_i&/le r^*/cdot /sum cost_i //r^*/cdot /sum cost_i -/sum value_i &/ge 0/end{aligned}$$

二分法

設(shè)當前答案r$r$， r<r?$r < r^*$，至少存在一個環(huán)，r?∑costi?∑valuei<0$r /cdot /sum cost_i -/sum value_i < 0$，即存在負權(quán)回路（將邊權(quán)設(shè)為r?costi?valuei$r/cdot cost_i-value_i$，不是提前算出，而是在更新路徑的時候從哪個點訪問到這條邊的就將這條邊設(shè)為相應(yīng)點權(quán)與邊權(quán)的對應(yīng)值）； r≥r?$r/ge r^*$，則不存在負環(huán)。

求負環(huán)可以用Bellman-Ford，但是比較慢，一般用spfa算法求負環(huán) 具體判斷方法為，一個點不能入隊n$n$次，否則有負環(huán)；一條最短路徑長度不能到n$n$，否則有負環(huán)。兩個判斷方法可以同時使用。

Dinkelbach$Dinkelbach$算法

如果用這個算法需要記錄下來一個負環(huán)，實現(xiàn)還是能實現(xiàn)的，但是沒有二分+spfa好寫。

例題

poj 3621(最優(yōu)比率環(huán))

問題模型4

最大密度子圖

這個問題會寫在網(wǎng)絡(luò)流總結(jié)中。

參考資料

【1】KirisameMarisa - NYIST 914Yougth的最大化【二分搜索/Dinkelbach算法】 【2】PerSeAwe - ［Algorithm］01分數(shù)規(guī)劃