算法
插入排序
- 每次將一個(gè)待排序的元素與已排序的元素進(jìn)行逐一比較，直到找到合適的位置按大小插入愚屁。
插入排序代碼
public static void insertsort(int arr[]){
for(int i = 1;i < arr.length; i ++){
if(arr[i] < arr[i-1]){
int temp = arr[i];
int j;
for(j = i-1; j >= 0 && arr[j] > temp; j --){
arr[j+1] = arr[j]; }
arr[j+1] = temp; }
}
}
注意[0,i-1]都是有序的呢诬。如果待插入元素比arr[i-1]還大則無需再與[i-1]前面的元素進(jìn)行比較了，反之則進(jìn)入if語句
快速排序
- 快速排序是找出一個(gè)元素（一般找最后一個(gè)）作為基準(zhǔn)(pivot),然后對數(shù)組進(jìn)行分區(qū)操作,使基準(zhǔn)左邊元素的值都不大于基準(zhǔn)值,基準(zhǔn)右邊的元素值 都不小于基準(zhǔn)值，如此作為基準(zhǔn)的元素調(diào)整到排序后的正確位置像街。遞歸快速排序，將其他n-1個(gè)元素也調(diào)整到排序后的正確位置晋渺。最后每個(gè)元素都是在排序后的正確位置镰绎，排序完成∧疚鳎快速排序算法的核心算法是分區(qū)操作畴栖，即如何調(diào)整基準(zhǔn)的位置以及調(diào)整返回基準(zhǔn)的最終位置以便分治遞歸。
快速排序JavaScript代碼
var quickSort = function(arr) {
if (arr.length <= 1) { return arr; }
var pivotIndex = Math.floor(arr.length / 2);
var pivot = arr.splice(pivotIndex, 1)[0];
var left = [];
var right = [];
for (var i = 0; i < arr.length; i++){
if (arr[i] < pivot) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
return quickSort(left).concat([pivot], quickSort(right));
};
動態(tài)規(guī)劃：
- 實(shí)質(zhì)上還是嘗試了所有可能的方案八千，只是從小到大按照需求的增加去得到每一個(gè)子問題的最優(yōu)解并記錄吗讶，后面的階段大問題對所有可能做嘗試并劃分成小的問題燎猛，直接利用小問題已知的最優(yōu)解帶入去和其他嘗試的結(jié)果去比較得到大問題的最優(yōu)解。在這個(gè)過程中不需要再去重復(fù)求解小問題的最優(yōu)解照皆。
- 鋼條的切割問題：不斷累加的是鋼條的長度重绷，在每一個(gè)長度內(nèi)嘗試所有的切割方式（即不斷累加切割的長度），嘗試比較后得到這個(gè)鋼條長度的最優(yōu)切割方式并保存膜毁。從小到大最后得到最終的最優(yōu)解昭卓。
- 01背包??問題：不斷增加的是背包的容量，在每一個(gè)長度內(nèi)嘗試放入一種物品（如果空間足夠）瘟滨，放入后剩余空間則放入對應(yīng)容量的最優(yōu)值候醒，比較放入物品后的總價(jià)值并記錄。最終得到大容量背包的最優(yōu)解杂瘸。
01??代碼
#include<stdlib.h>
#include<stdio.h>
int V[200][200];//前i個(gè)物品裝入容量為j的背包中獲得的最大價(jià)值
int max(int a,int b) //一個(gè)大小比較函數(shù)倒淫，用于當(dāng)總重大于第I行時(shí)
{
if(a>=b)
return a;
else return b;
}
int Knap(int n,int w[],int v[],int x[],int C)
{
int i,j;
for(i=0;i<=n;i++)
V[i][0]=0;
for(j=0;j<=C;j++)
V[0][j]=0;
for(i=0;i<=n-1;i++)
for(j=0;j<=C;j++)
if(j<w[i])
V[i][j]=V[i-1][j];
else
V[i][j]=max(V[i-1][j],V[i-1][j-w[i]]+v[i]);
j=C;
for(i=n-1;i>=0;i--)
{
if(V[i][j]>V[i-1][j])
{
x[i]=1;
j=j-w[i];
}
else
x[i]=0;
}
printf("選中的物品是: \n");
for(i=0;i<n;i++)
printf("%d ",x[i]);
printf("\n");
return V[n-1][C];
}
貪婪算法
- 分式背包??問題: 首先應(yīng)計(jì)算物品在單位體積下的價(jià)值，先獲取單位價(jià)值最大的物品败玉，未滿的情況下繼續(xù)添加單位價(jià)值第二大的物品昌简，直至背包填滿：:
最大流
- 從源點(diǎn)到經(jīng)過的所有路徑的最終到達(dá)匯點(diǎn)的所有流量和。
流網(wǎng)絡(luò)G=(V,E)是一個(gè)有向圖绒怨，其中每條邊(u,v)∈E均有一個(gè)非負(fù)容量c(u,v)>=0纯赎。如果(u,v)不屬于E，則假定c(u,v)=0南蹂。流網(wǎng)絡(luò)中有兩個(gè)特別的頂點(diǎn)：源點(diǎn)s和匯點(diǎn)t犬金。下圖展示了一個(gè)流網(wǎng)絡(luò)的實(shí)例（其中斜線左邊的數(shù)字表示實(shí)際邊上的流，右邊的數(shù)字表示邊的最大容量）： - Alt text
- 對一個(gè)流網(wǎng)絡(luò)G=(V,E)六剥，其容量函數(shù)為c晚顷，源點(diǎn)和匯點(diǎn)分別為s和t。G的流f滿足下列三個(gè)性質(zhì)：
1. 容量限制：對所有的u疗疟，v∈V该默，要求f(u,v)<=c(u,v)。
2. 反對稱性：對所有的u策彤，v∈V栓袖，要求f(u,v)=-f(v,u)。
3. 流守恒性：對所有u∈V-{s,t}店诗，要求∑f(u,v)=0 (v∈V)裹刮。
*容量限制說明了從一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)的網(wǎng)絡(luò)流不能超過設(shè)定的容量
在給定的流網(wǎng)絡(luò)G=(V,E)中，設(shè)f為G中的一個(gè)流庞瘸，并考察一對頂點(diǎn)u捧弃，v∈V，在不超過容量c(u,v)的條件下，從u到v之間可以壓入的額外網(wǎng)絡(luò)流量违霞，就是(u,v)的殘留容量嘴办，就好像某一個(gè)管道的水還沒有超過管道的上限，那么就這條管道而言买鸽，就一定還可以注入更多的水涧郊。殘留容量的定義為：cf(u,v)=c(u,v)-f(u,v)。而由所有屬于G的邊的殘留容量所構(gòu)成的帶權(quán)有向圖就是G的殘留網(wǎng)絡(luò)癞谒。下圖就是上面的流網(wǎng)絡(luò)所對應(yīng)的殘留網(wǎng)絡(luò)：
- Alt text
殘留網(wǎng)絡(luò)中的邊既可以是E中邊底燎，也可以是它們的反向邊。只有當(dāng)兩條邊(u,v)和(v,u)中弹砚，至少有一條邊出現(xiàn)在初始網(wǎng)絡(luò)中時(shí)双仍，邊(u,v)才會出現(xiàn)在殘留網(wǎng)絡(luò)中。下面是一個(gè)有關(guān)殘留網(wǎng)絡(luò)的定理桌吃，若f是G中的一個(gè)流朱沃，Gf是由G導(dǎo)出的殘留網(wǎng)絡(luò)，f'是Gf中的一個(gè)流茅诱，則f+f'是G中一個(gè)流逗物，且其值|f+f'|=|f|+|f'|。證明時(shí)只要證明f+f'這個(gè)流在G中滿足之前所講述的三個(gè)原則即可瑟俭。在這里只給出理解性的證明翎卓，可以想象如果在一個(gè)管道中流動的水的總流量為f，而在該管道剩余的流量中存在一個(gè)流f'可以滿足不會超過管道剩余流量的最大限摆寄，那么將f和f'合并后失暴，也必定不會超過管道的總流量，而合并后的總流量值也一定是|f|+|f'|微饥。
增廣路徑p為殘留網(wǎng)絡(luò)Gf中從s到t的一條簡單路徑逗扒。根據(jù)殘留網(wǎng)絡(luò)的定義，在不違反容量限制的條件下欠橘，G中所對應(yīng)的增廣路徑上的每條邊(u,v)可以容納從u到v的某額外正網(wǎng)絡(luò)流矩肩。而能夠在這條路徑上的網(wǎng)絡(luò)流的最大值一定是p中邊的殘留容量的最小值。這還是比較好理解的肃续，因?yàn)槿绻鹥上的流大于某條邊上的殘留容量黍檩，必定會在這條邊上出現(xiàn)流聚集的情況。所以我們將最大量為p的殘留網(wǎng)絡(luò)定義為：cf(p)=min{cf(u,v) | (u,v)在p上}痹升。而結(jié)合之前在殘留網(wǎng)絡(luò)中定理建炫，由于p一定是殘留網(wǎng)絡(luò)中從s到t的一條路徑，且|f'|=cf(p)疼蛾，所以若已知G中的流f，則有|f|+|cf(p)|>|f|且|f|+|cf(p)|不會超過容量限制艺配。
-
流網(wǎng)絡(luò)G(V,E)的割(S,T)將V劃分成為S和T=V-S兩部分察郁，使得s∈S衍慎，t∈T。如果f是一個(gè)流皮钠，則穿過割(S,T)的凈流被定義為f(S,T)=∑f(x,y) (x∈S,y∈T)稳捆，割(S,T)的容量為c(S,T)。一個(gè)網(wǎng)絡(luò)的最小割就是網(wǎng)絡(luò)中所有割中具有最小容量的割麦轰。設(shè)f為G中的一個(gè)流乔夯，且(S,T)是G中的一個(gè)割，則通過割(S,T)的凈流f(S,T)=|f|款侵。因?yàn)閒(S,T)=f(S,V)-f(S,S)=f(S,V)=f(s,V)+f(S-s,V)=f(s,V)=|f|（這里的公式根據(jù)f(X,Y)=∑f(x,y) (x∈X,y∈Y)的定義末荐，以及前面的三個(gè)限制應(yīng)該還是可以推出來的，這里就不細(xì)講了）新锈。有了上面這個(gè)定理甲脏，我們可以知道當(dāng)把流不斷增大時(shí)，流f的值|f|不斷的接近最小割的容量直到相等妹笆，如果這時(shí)可以再增大流f块请，則f必定會超過某個(gè)最小的割得容量，則就會存在一個(gè)f(S,T)<=c(S,T)<|f|拳缠，顯然根據(jù)上面的定理這是不可能墩新。所以最大流必定不超過網(wǎng)絡(luò)最小割的容量。
綜合上面所講窟坐，有一個(gè)很重要的定理：最大流最小割定理 如果f是具有源s和匯點(diǎn)t的流網(wǎng)絡(luò)G=(V,E)中的一個(gè)流海渊，則下列條件是等價(jià)的：
1. f是G中一個(gè)最大流。
2. 殘留網(wǎng)絡(luò)Gf不包含增廣路徑狸涌。
3. 對G的某個(gè)割(S,T)切省，有|f|=c(S,T)。
#include <iostream>
#include <queue>
#include<string.h>
using namespace std;
#define arraysize 201
int maxData = 0x7fffffff;
int capacity[arraysize][arraysize]; //記錄殘留網(wǎng)絡(luò)的容量
int flow[arraysize]; //標(biāo)記從源點(diǎn)到當(dāng)前節(jié)點(diǎn)實(shí)際還剩多少流量可用
int pre[arraysize]; //標(biāo)記在這條路徑上當(dāng)前節(jié)點(diǎn)的前驅(qū),同時(shí)標(biāo)記該節(jié)點(diǎn)是否在隊(duì)列中
int n,m;
queue<int> myqueue;
int BFS(int src,int des)
{
int i,j;
while(!myqueue.empty()) //隊(duì)列清空
myqueue.pop();
for(i=1;i<m+1;++i)
{
pre[i]=-1;
}
pre[src]=0;
flow[src]= maxData;
myqueue.push(src);
while(!myqueue.empty())
{
int index = myqueue.front();
myqueue.pop();
if(index == des) //找到了增廣路徑
break;
for(i=1;i<m+1;++i)
{
if(i!=src && capacity[index][i]>0 && pre[i]==-1)
{
pre[i] = index; //記錄前驅(qū)
flow[i] = min(capacity[index][i],flow[index]); //關(guān)鍵：迭代的找到增量
myqueue.push(i);
}
}
}
if(pre[des]==-1) //殘留圖中不再存在增廣路徑
return -1;
else
return flow[des];
}
int maxFlow(int src,int des)
{
int increasement= 0;
int sumflow = 0;
while((increasement=BFS(src,des))!=-1)
{
int k = des; //利用前驅(qū)尋找路徑
while(k!=src)
{
int last = pre[k];
capacity[last][k] -= increasement; //改變正向邊的容量
capacity[k][last] += increasement; //改變反向邊的容量
k = last;
}
sumflow += increasement;
}
return sumflow;
}
int main()
{
int i,j;
int start,end,ci;
while(cin>>n>>m)
{
memset(capacity,0,sizeof(capacity));
memset(flow,0,sizeof(flow));
for(i=0;i<n;++i)
{
cin>>start>>end>>ci;
if(start == end) //考慮起點(diǎn)終點(diǎn)相同的情況
continue;
capacity[start][end] +=ci; //此處注意可能出現(xiàn)多條同一起點(diǎn)終點(diǎn)的情況
}
cout<<maxFlow(1,m)<<endl;
}
return 0;
}
bool EK_Bfs (int start, int end)//廣搜用于找增廣路帕胆；
{
bool flag[Maxn];//標(biāo)記數(shù)組
memset (flag, false, sizeof(flag));
memset (p, -1, sizeof(p));
flag[start] = true;
queue t;
t.push(start);
while (!t.empty())
{
int top = t.front();
if (top == end)return true;// 此時(shí)找到增廣路
t.pop();
for (int i=1; i<=n; i++)
{
if (map[top][i] && !flag[i])
{
flag[i] = true;
t.push(i);
p[i] = top;// 記錄前驅(qū)（很關(guān)鍵）
}
}
}
return false;
}
int E_K (int start,int end)
{
int u,max = 0,mn;//max用來初始化最大流為0;
while (EK_Bfs(start,end))//當(dāng)增廣成功時(shí)
{
mn = 100000;
u = end;
while (p[u] != -1)//尋找”瓶頸“邊朝捆，并且記錄容量;
{
mn = min (mn, map[p[u]][u]);
u = p[u];
}
max += mn;//累加邊的最大流;
u = end;
while (p[u] != -1)//修改路徑上的邊容量；
{
map[p[u]][u] -= mn;
map[u][p[u]] += mn;
u = p[u];
}
}
return max;
}
