摘要
?? ? 1.01背包問(wèn)題：有n個(gè)物品和一個(gè)容量為c的背包，從n個(gè)物品中選取裝包的物品毫痕。物品i的重量為wi征峦，價(jià)值為pi。一個(gè)最佳背包裝載指消请，物品總價(jià)值最高的可行背包裝載栏笆。max(sum(pi*xi)),約束條件是sum(wi*xi)<=c,xi的01表示物品是否放入背包。? ?
? ? 2.所有定點(diǎn)對(duì)之間的最短路徑：所有頂點(diǎn)對(duì)之間的最短路徑問(wèn)題是指向有向圖G臊泰，尋找每一對(duì)頂點(diǎn)之間的最短路徑蛉加。即對(duì)于每對(duì)頂點(diǎn)（i，j）,要尋找頂點(diǎn)i到頂點(diǎn)以及從頂點(diǎn)j到頂點(diǎn)i的最短路徑缸逃。
? ? 3 .網(wǎng)組的無(wú)交叉子集：給定一個(gè)上下兩邊有n個(gè)針腳的布線通道和一個(gè)排列C针饥。頂部的針腳i與底部的Ci相連。數(shù)對(duì)（i需频，Ci）稱為網(wǎng)組丁眼。總共有n個(gè)網(wǎng)組需連接或連通昭殉。假定有兩個(gè)或更多布線層苞七，其中一個(gè)為優(yōu)先層。其連線更細(xì)挪丢，電阻更小蹂风。任務(wù)是盡可能把更多的網(wǎng)組布設(shè)在優(yōu)先層，尋找一個(gè)最大無(wú)交叉子集乾蓬。
解決
1.建立背包問(wèn)題的動(dòng)態(tài)規(guī)劃遞歸公式惠啄。返回值是發(fā)f(1,c)的值，利用全局變量profit,weight和numberofobjects。物體價(jià)值和重量分別用profit[1:numberofobjects]和weight[1:numberofobjects]來(lái)表示撵渡。
遞歸函數(shù)：
int f(int i, int thecapacity)
? ? if (i==numberofobjects)
return(thecapacity
? ? if(thecapacity
return f(i+1,thecapacity);
return max(f(i+1,thecapacity),f(i+1,thecapacity-weight[i])+profit[i]);
? 完整算法：
#include
#include
int V[200][200];//前i個(gè)物品裝入容量為j的背包中獲得的最大價(jià)值
int max(int a, int b)
{
? ? if (a >= b) return a;
? ? else return b;
}
int KnapSack(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; i++){
? ? ? ? for (j = 0; j < C+1; j++){
? ? ? ? ? ? if (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
? ? ? ? printf("%d ", x[i]);
? ? printf("\n");
? ? for (int i = 0; i < n; i++){
? ? ? ? for (int j = 0; j < C+1; j++){
? ? ? ? ? ? printf("%d\t ", V[i][j]);
? ? ? ? ? ? if (j == C){
? ? ? ? ? ? ? ? printf("\n");
? ? ? ? ? ? }
? ? ? ? }
? ? }
? ? return V[n - 1][C];
}
int main()
{
? ? int s;//獲得的最大價(jià)值
? ? int w[5] = {2,2,6,5,4};//物品的重量
? ? int v[5] = {6,3,5,4,6};//物品的價(jià)值
? ? int x[5];//物品的選取狀態(tài)
? ? int n = 5;
? ? int C=10;//背包最大容量
? ? s = KnapSack(n, w, v, x, C);
? ? printf("最大物品價(jià)值為:\n");
? ? printf("%d\n", s);
? ? system("pause");
? ? return 0;
}
2.所有頂點(diǎn)對(duì)之間的最短路徑：當(dāng)邊上的權(quán)都不是負(fù)值的時(shí)候融柬，所有頂點(diǎn)對(duì)之間的最短路徑可以用dijkstra單源算法n次來(lái)求解，每一次都選擇n個(gè)頂點(diǎn)中的一個(gè)頂點(diǎn)作為源點(diǎn)姥闭。這個(gè)過(guò)程的時(shí)間復(fù)雜度為O(n^3)〉ず瑁現(xiàn)采用foly算法，相關(guān)的常數(shù)因子比Dijkstra算法要小棚品。
? ? 假設(shè)G中有n個(gè)頂點(diǎn)，從1到n編號(hào)廊敌。c(i,j,k)表示從頂點(diǎn)i到j(luò)到一條最短路徑的長(zhǎng)度铜跑，其中間頂點(diǎn)的編號(hào)不都大于k。因此骡澈，如果邊(i,j)存在锅纺，則c(i,j,0)是該邊的長(zhǎng)度。若i=j,則c(i,j,0)為0肋殴。如果邊(i,j)不存在囤锉，則c(i,j,0)等于∞。c(i,j,n)是從i到j(luò)的最短路徑的長(zhǎng)度护锤。
偽代碼：
for (int i=1; j
? for(int j=1;j
? c(i, j, k)=a(i, j);
for(int k=1, k<=n; k++)
? for(int i=1;i<=n;i++)
for(int j=1;j<=n; j++)
if (c(i, k, k-1)+c(k, j, k-1)
? ? c(i, j, k)=c(i, k, k-1)+c(k, j, k-1);
else c(i, j, k)=c(i, j, k-1);
? ? ? ? Template
void allpairs(T **c, int **kay)
{
? ? ? for (int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
{
c[i][j]=a[i][j];
kay[i][j]=0;
}
for (int i=1; i<=n; i++)
? c[i][i]=0;
for(int k=1; k<=n; k++)
? for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
if (c[i][k]!=noEdge&&c[k][j]!=noEdge&&
(c[i][j]==noEdge||c[i][j]>c[i][k]+c[k][j]))
{
c[i][j]=c[i][k]+c[k][j];
kay[i][j]=k;
}}
3.網(wǎng)組的無(wú)交叉子集：令MNS(i,j)代表一個(gè)MNS官地，其中所有的網(wǎng)組(u,Cu)滿足u<=i,Cu<=j。令size(i,j)表示MNS(i,j)的大小烙懦。MNS(n,n)是對(duì)應(yīng)于輸入實(shí)例的一個(gè)MNS驱入。
j=C1, size(1,j)=1.
j
j<=Ci, size(i, j)=max{size(i-1,j),size(i-1,Ci-1)+1}
偽代碼：(查找網(wǎng)絡(luò)中最大的無(wú)交叉子集)
int traceback(int *c, int numberofnets, int **size, int *net)
{
int sizeofmns=0;
for (int i=numberofnets; i>1; i- -)
if(size[i][maxalllowed]!=size[i-1][maxallowed])
{
net[sizeofmns++]=i;
maxallowed=c[i]-1;
}
if(maxallowed>=c[1])
? ? net[sizeofmns++]=i;
}
總結(jié)
動(dòng)態(tài)規(guī)劃算法通常用于求解具有某種最優(yōu)性質(zhì)的問(wèn)題。在這類問(wèn)題中氯析，可能會(huì)有許多可行解亏较。每一個(gè)解都對(duì)應(yīng)于一個(gè)值，我們希望找到具有最優(yōu)值的解掩缓。動(dòng)態(tài)規(guī)劃算法與分治法類似雪情，其基本思想也是將待求解問(wèn)題分解成若干個(gè)子問(wèn)題，先求解子問(wèn)題你辣，然后從這些子問(wèn)題的解得到原問(wèn)題的解巡通。
與分治法不同的是，經(jīng)動(dòng)態(tài)規(guī)劃分解得到子問(wèn)題往往不是互相獨(dú)立的绢记。如果我們能夠保存已解決的子問(wèn)題的答案扁达，需要時(shí)再找出已求得的答案，可避免重復(fù)計(jì)算蠢熄，節(jié)省時(shí)間跪解。可用表來(lái)記錄所有已解的子問(wèn)題的答案。不管該子問(wèn)題以后是否被用到叉讥，只要它被計(jì)算過(guò)窘行，就將其結(jié)果填入表中。這就是動(dòng)態(tài)規(guī)劃法的基本思路图仓。
適用動(dòng)態(tài)規(guī)劃的問(wèn)題必須滿足最優(yōu)化原理和無(wú)后效性和子問(wèn)題的重疊性罐盔。
文獻(xiàn)引用
? 《數(shù)據(jù)結(jié)構(gòu)算法與應(yīng)用：c++語(yǔ)言描述》
?? “CSDN博客摘要 ”
?? 《C語(yǔ)言教程》
????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????Jason?
????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????18.8.8
