[ 0-1 Fractional Programming Dinkelbach algorithm ] 0-1分數規劃

【定義】

給你兩個數組，$benefit[i]$表示選$i$的利潤、$cost[i]$表示選$i$的花費。
如果選$i$，定義$x[i]=1$否則$x[i]=0$，通常題目會給你選擇的限制條件，像是必須是一顆生成樹之類的，這裡就把它忽略掉
我們的目標是要求$\frac{\sum{benefit[i] \times x[i]}}{\sum{cost[i] \times x[i]}}$的最大值。

【分析】

先不管最大化問題，令$\frac{\sum{benefit[i] \times x[i]}}{\sum{cost[i] \times x[i]}}=L$
可以把式子改寫成$(\sum{benefit[i] \times x[i]})-L \times (\sum{cost[i] \times x[i]})=0$
分離參數得到$\sum{(benefit[i]-L \times  cost[i]) \times x[i]}=0$
只要知道$L$，$(benefit[i]-L \times  cost[i])$是直接可以求出來的，先記他為$d(i,L)$吧
那可以設$f(L)=\sum{d(i,L) \times x[i]}$

我們的目標變成是要最大化$L$
那若存在一種$x$的選法使得$f(L)>0$能夠證明什麼呢?
$f(L)>0 \to \frac{\sum{benefit[i] \times x[i]}}{\sum{cost[i] \times x[i]}}>L$那表示存在另一個$L$會比現在的$L$還要好
那 $f(L)<0$?很明顯這種情況完全沒有意義，因為找不到這種$L$

最佳的$L$會讓所有$x$的選法都$f(L)\leq0$，只要找到這樣的$L$就說明他是最佳解了
也可以用類似的想法求最小化$L$，這裡就不贅述了。

【解法】

根據剛剛找出來的性質$f(L)$是單調性的，我們可以二分搜$L$，然後驗證是否存在一組解使得$f(L)>0$，這很簡單就不附code了。
另一個有效率的算法是Dinkelbach，他跟二分搜不一樣的地方是他要去求解，在驗證解跟求解的複雜度一樣的時候Dinkelbach是會比較快的，但有時候求解的複雜度會比驗證解的複雜度還要高，因此要看情況使用
以下附上虛擬碼：

	Dinkelbach(){
	L=任意狀態(通常設為0);
	do{
	Ans=L;
	for(i:所有元素)d[i]=benefit[i]-L*cost[i];//計算d值
	找出一組使f(L)最大的x;
	p=0,q=0;
	for(i:所有元素){
	if(x[i])p+=benefit[i],q+=cost[i];
	}
	L=p/q;//更新解，注意q=0的情況
	}while(abs(Ans-L)>EPS);
	return Ans;
	}

view raw Dinkelbach.cpp hosted with ❤ by GitHub

常見的題型有：最優比率環、最優比率生成樹、最大密度子圖(有flow解)等