總結(jié)下01分?jǐn)?shù)規(guī)劃：
01分?jǐn)?shù)規(guī)劃通常分為三類(lèi)
（1）基礎(chǔ)01分?jǐn)?shù)規(guī)劃 (模板題:poj2976)
（2）最優(yōu)比率生成樹(shù) (模板題:poj2728)
（3）最優(yōu)比率生成環(huán) (模板題:自己找)(這個(gè)比較難,還是多多研究吧)
首先01分?jǐn)?shù)規(guī)劃是處理這樣一類(lèi)問(wèn)題的，給你n個(gè)二元組，這個(gè)兩個(gè)元素設(shè)為a[i] ,b[i], a[i]是得到這
個(gè)物品所能得到的價(jià)值，b[i]是得到這個(gè)物品所付出的價(jià)值，讓你求這樣一個(gè)極值
R = sigma(a[i] * x[i]) / sigma(b[i] * x[i])求他的最大或最小，這里我們以最大為例說(shuō)事。
設(shè) F(L) = sigma(a[i] * x[i]) - L * sigma(b[i] * x[i]) //注意此時(shí)的L和R的關(guān)系，其實(shí)L == R .
化簡(jiǎn) = sigma((a[i] - L * b[i]) * x[i])
設(shè) d[i] = a[i] - L * b[i]
則 F(L) = sigma(d[i] * x[i])
F(L)到底到底有什么用呢？
我們假設(shè)F(L) > 0 則有 sigma(a[i] * x[i]) - L * sigma(b[i] * x[i]) > 0
轉(zhuǎn)化后得到 sigma(a[i] * x[i]) / sigma(b[i] * x[i]) > L
也就是說(shuō)當(dāng)F(L) > 0 的時(shí)候有更大的L，也就是有更大的R，那么只要F(L) > 0我們就可以直接去
找更大的L（R）直到F(L) 無(wú)限接近0為止，這里我們可以用二分去查找，理由是
F(L) = sigma(d[i] * x[i]) ，d[i] 又是隨著L增加而減少的(所以隨著L增大,一定有一個(gè)點(diǎn)使得F(L) ==0 ，
這時(shí)再增大的話,就會(huì)導(dǎo)致F(L) < 0 [即L<0]，此時(shí)的F(L) 沒(méi)有實(shí)際意義,因?yàn)長(zhǎng)不可能小于0，參數(shù)都
是正的嘛)，只要能找到一種sigma(d[i] * x[i])>=0的情況我們就可以繼續(xù)往上找，說(shuō)道這里直接分細(xì)
化，上面說(shuō)只要找到一組d[i]>=0的就可以low = mid 往上找了，這里到底有沒(méi)有限制呢，當(dāng)然有，限制就是上面的那三個(gè)分類(lèi)，
（1）正常的情況（沒(méi)有任何限制的）我們只要找到一個(gè)最大的d[i]，d[i]>= 0就行了
因?yàn)槭侵灰业揭环N情況就行,我們沒(méi)必要多找,但是前兩天見(jiàn)到一個(gè)是限制必須選擇n - k個(gè)的，那么就把現(xiàn)有的d[i]求出來(lái)，
排序，取最大的那n-k個(gè)的和，看大是否大于等于0就行了（POJ 2976）
（2）最優(yōu)比率生成樹(shù)，就是在我們選擇的時(shí)候要找到一顆滿足要求的數(shù)而已，一般都是求最小樹(shù)
或者最大樹(shù)，然后看權(quán)值是否>=0.（POJ 2728）
（3）最優(yōu)比率生成環(huán)，就是要求我們選擇一個(gè)環(huán)，這個(gè)我習(xí)慣用SPFA,判斷滿足要求的環(huán)
（POJ 3621）
數(shù)學(xué)分析中一個(gè)很重要的方法就是分析目標(biāo)式，這樣我們來(lái)看目標(biāo)式。
R=sigma(a[i]*x[i])/sigma(b[i]*x[i])
我們來(lái)分析一下他有什么性質(zhì)可以給我們使用。
我們先定義一個(gè)函數(shù)F(L):=sigma(a[i]*x[i])-L*sigma(b[i]*x[i])，顯然這只是對(duì)目標(biāo)式的一個(gè)簡(jiǎn)單
的變形。分離參數(shù)，得到F(L):=sigma((a[i]-L*b[i])*x[i])。這時(shí)我們就會(huì)發(fā)現(xiàn)，如果L已知的話，
a[i]-L*b[i]就是已知的，當(dāng)然x[i]是未知的。記d[i]=a[i]-L*b[i]，那么F(L):=sigma(d[i]*x[i])，多么簡(jiǎn)
潔的式子。我們就對(duì)這些東西下手了。
再次提醒一下，我們的目標(biāo)是使R取到最大值。
我們來(lái)分析一下這個(gè)函數(shù)，它與目標(biāo)式的關(guān)系非常的密切，L就是目標(biāo)式中的R，最大化R也就
是最大化L。
F的值是由兩個(gè)變量共同決定的，即方案X和參數(shù)L。對(duì)于一個(gè)確定的參數(shù)L來(lái)說(shuō)，方案的不同
會(huì)導(dǎo)致對(duì)應(yīng)的F值的不同，那么這些東西對(duì)我們有什么用呢?
假設(shè)我們已知在存在一個(gè)方案X使得F(L)>0，這能夠證明什么?
F(L)=sigma(a[i]*x[i])-L*sigma(b[i]*x[i])>0即sigma(a[i]*x[i])/sigma(b[i]*x[i])>L也就是說(shuō)，如果一
個(gè)方案使得F(L)>0說(shuō)明了這組方案可以得到一個(gè)比現(xiàn)在的L更優(yōu)的一個(gè)L，既然有一個(gè)更優(yōu)的
解，那么為什么不用呢？
顯然，d數(shù)組是隨著L的增大而單調(diào)減的。也就是說(shuō)，存在一個(gè)臨界的L使得不存在一種方案，
能夠使F(L)>0. 我們猜想，這個(gè)時(shí)候的L就是我們要求的最優(yōu)解。之后更大的L值則會(huì)造成無(wú)論
任何一種方案，都會(huì)使F(L)<0.類(lèi)似于上面的那個(gè)變形，我們知道，F(xiàn)(L)<0是沒(méi)有意義的，因
為這時(shí)候的L是不能夠被取得的。當(dāng)F(L)=0使，對(duì)應(yīng)方案的R值恰好等于此時(shí)的L值。
綜上，函數(shù)F(L)有這樣的一個(gè)性質(zhì)：在前一段L中可以找到一組對(duì)應(yīng)的X使得F(L)>0，這就提
供了一種證據(jù)，即有一個(gè)比現(xiàn)在的L更優(yōu)的解，而在某個(gè)L值使，存在一組解使得F(L)=0,且其
他的F(L)<0，這時(shí)的L無(wú)法繼續(xù)增大，即這個(gè)L就是我們期望的最優(yōu)解，之后的L會(huì)使得無(wú)論哪
種方案都會(huì)造成F(L)<0.而我們已經(jīng)知道，F(xiàn)(L)<0是沒(méi)有任何意義的，因?yàn)榇藭r(shí)的L值根本取不
到。
最后一次提醒，我們的目標(biāo)是R?。。?
如果現(xiàn)在你覺(jué)得有些暈的話，那么我要提醒你的就是，千萬(wàn)不要把F值同R值混淆。F值是根據(jù)
我們的變形式求的D數(shù)組來(lái)計(jì)算的，而R值則是我們所需要的真實(shí)值，他的計(jì)算是有目標(biāo)式?jīng)Q
定的。F值只是提供了一個(gè)證據(jù)，告訴我們真正最優(yōu)的R值在哪里，他與R值本身并沒(méi)有什么必
然的聯(lián)系。
根據(jù)這樣的一段性質(zhì)，很自然的就可以想到二分L值，然后驗(yàn)證是否存在一組解使得F(L)>0，有就移動(dòng)下界，沒(méi)有就移動(dòng)上界。
所有的01分?jǐn)?shù)規(guī)劃都可以這么做，唯一的區(qū)別就在于求解時(shí)的不同——因?yàn)槊恳坏李}的限制
條件不同，并不是每一個(gè)解都是可行解的。比如在普通的數(shù)組中，你可以選取1、2、3號(hào)元
素，但在生成樹(shù)問(wèn)題中，假設(shè)1、2、3號(hào)元素恰好構(gòu)成了一個(gè)環(huán)，那就不能夠同時(shí)選擇了，這
就是需要具體問(wèn)題，具體分析的部分。
二分是一個(gè)非常通用的辦法，但是我們來(lái)考慮這樣的一個(gè)問(wèn)題，二分的時(shí)候我們只是用到了F
(L)>0這個(gè)條件，而對(duì)于使得F(L)>0的這組解所求到的R值沒(méi)有使用。因?yàn)镕(L)>0,我們已經(jīng)知
道了R是一個(gè)更優(yōu)的解，與其漫無(wú)目的的二分，為什么不將解移動(dòng)到R上去呢？求01分?jǐn)?shù)規(guī)劃
的另一個(gè)方法就是
，他就是基于這樣的一個(gè)思想，他并不會(huì)去二分答案，而是先隨便給定一個(gè)答案，然后根據(jù)更
優(yōu)的解不斷移動(dòng)答案，逼近最優(yōu)解。由于他對(duì)每次判定使用的更加充分，所以它比二分會(huì)快上
很多。但是，他的弊端就是需要保存這個(gè)解，而我們知道，有時(shí)候驗(yàn)證一個(gè)解和求得一個(gè)解的
復(fù)雜度是不同的。二分和Dinkelbach算法寫(xiě)法都非常簡(jiǎn)單，各有長(zhǎng)處，大家要根據(jù)題目謹(jǐn)慎使
用。
