總結(jié)下01分?jǐn)?shù)規(guī)劃：


01分?jǐn)?shù)規(guī)劃通常分為三類
（1）基礎(chǔ)01分?jǐn)?shù)規(guī)劃
（2）最優(yōu)比率生成樹
（3）最優(yōu)比率生成環(huán)


首先01分?jǐn)?shù)規(guī)劃是處理這樣一類問題的，給你n個二元組，這個兩個元素設(shè)為a[i] ,b[i], a[i]是得到這個物品所能得到的價值，b[i]是得到這個物品所付出的價值，讓你求這樣一個極值
? ? R ?= ?sigma(a[i] * x[i]) / sigma(b[i] * x[i])求他的最大或最小，這里我們以最大為例說事。


設(shè) F(L) = sigma(a[i] * x[i]) - L * sigma(b[i] * x[i])//注意此時的L和R的關(guā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
? ? 也就是說當(dāng)F(L) > 0 的時候有更大的L，也就是有更大的R，那么只要F(L) > 0我們就可以直接去找更大的L（R）直到F(L) 無限接近0為止，這里我們可以用二分去查找，理由是
F(L) = sigma(d[i] * x[i]) ，d[i] 又是隨著L增加而減少的，只要能找到一種
sigma(d[i] * x[i])>=0的情況我們就可以繼續(xù)往上找，說道這里直接分細(xì)化，上面說只要找到一組d[i]>=0的就可以low = mid 往上找了，這里到底有沒有限制呢，當(dāng)然有，限制就是上面的那三個分類，
（1）正常的情況（沒有任何限制的）我們只要找到一個最大的d[i]，d[i]>= 0就行了，因為是只要找到一種情況就行，我們沒必要多找，但是前兩天見到一個是限制必須選擇n - k個的，那么就把雖有的d[i]求出來，排序，取最大的那n-k個的和，看大是否大于等于0就行了（POJ 2976）
（2）最優(yōu)比率生成樹，就是在我們選擇的時候要找到一顆滿足要求的數(shù)而已，一般都是求最小樹或者最大樹，然后看權(quán)值是否>=0.（POJ 2728）
（3）最優(yōu)比率生成環(huán)，就是要求我們選擇一個環(huán)，這個我習(xí)慣用SPFA,判斷滿足要求的環(huán)
（POJ 3621）


給個算法的模板吧，一共兩個算法，我只寫二分的那個吧。




double low = ,up = ,mid;
ans = 0;
while(up - low >= eps)
{
? ? mid = (low + up) / 2;
? ? if(jude(mid)) //jude()函數(shù)根據(jù)是三種中的哪個個類型而定。
? ? ans = low = mid;
? ? else up = mid;
}

總結(jié)

以上是生活随笔為你收集整理的总结01分数规划的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。