01分?jǐn)?shù)規(guī)劃

$N$個(gè)物品選$k$個(gè)，最大化：

$\frac{\sum\limits_{i=1}^{k}A_i}{\sum\limits_{i=1}^{k}B_i}$

二分答案$mid$

如果

$\sum\limits_{i=1}^{k}{A_i-mid*B_i}\ >\ 0$

則可以更優(yōu)

顯然是要選擇$A_i-mid*B_i$的前$k$大

?

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

最小化生成樹(shù)的$n$條邊

$\frac{\sum\limits_{i,j=1}^{n}cost(i,j)}{\sum\limits_{i,j=1}^{n}Dis(i,j)}$

一樣的做法二分答案每次求最小生成樹(shù)

然后完全圖用$Kruskal$多一個(gè)$log$，還是用$Prim\ Naive$好(你以為我會(huì)告訴你我現(xiàn)學(xué)的$Prim$嘛)

?

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

找一個(gè)環(huán)，最大化某個(gè)條件

二分答案，在圖上轉(zhuǎn)化為負(fù)環(huán)

$spfa$判斷負(fù)環(huán)：

$1.$普通$BFS$做法,可以先把所有點(diǎn)加到隊(duì)列里,$d[i]=0$

$2.$$DFS$做法,$d[i]=0$,枚舉每個(gè)點(diǎn)開(kāi)始$DFS$，看看會(huì)不會(huì)形成環(huán)

double d[N]; int vis[N],cl; bool dfs(int u,double mid){vis[u]=cl;for(int i=h[u];i;i=e[i].ne){int v=e[i].v;double w=mid*e[i].w-f[u];if(d[v]>d[u]+w){d[v]=d[u]+w;if(vis[v]==vis[u]) return true;else if(dfs(v,mid)) return true;}}vis[u]=0;return false; } bool NegativeCircle(double mid){memset(vis,0,sizeof(vis));for(cl=1;cl<=n;cl++) if(dfs(cl,mid)) return true;return false; } DFS

?

最大權(quán)密度子圖

$Maximize D=\frac{\sum\limits_{e \in E}x_e}{\sum\limits_{v \in V}x_v}$
$x_e,x_v \in {0,1}$
$\forall e=(u,v) \in E,\ u,v \in V$

同樣二分答案$g$，然后判斷
$\sum\limits_{e \in E}x_e\ -\ \sum\limits_{v \in V}x_v*g\ >\ 0$則可以更優(yōu)
二分查找范圍$[m,\frac{1}{n}]$,精度$\frac{1}{n^2}$
求解二分查找后式子的最大值使用最大權(quán)閉合子圖，選一條邊則必須選擇兩個(gè)頂點(diǎn)
$s--1-->e--INF-->u,v--g-->t$

總結(jié)

以上是生活随笔為你收集整理的[01分数规划]【学习笔记】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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