摘要
1.01背包问题：有n个物品和一个容量为c的背包，从n个物品中选取装包的物品。物品i的重量为wi，价值为pi。一个最佳背包装载指，物品总价值最高的可行背包装载。max(sum(pi*xi)),约束条件是sum(wi*xi)<=c,xi的01表示物品是否放入背包。
2.所有定点对之间的最短路径：所有顶点对之间的最短路径问题是指向有向图G，寻找每一对顶点之间的最短路径。即对于每对顶点（i，j）,要寻找顶点i到顶点以及从顶点j到顶点i的最短路径。
3 .网组的无交叉子集：给定一个上下两边有n个针脚的布线通道和一个排列C。顶部的针脚i与底部的Ci相连。数对（i，Ci）称为网组。总共有n个网组需连接或连通。假定有两个或更多布线层，其中一个为优先层。其连线更细，电阻更小。任务是尽可能把更多的网组布设在优先层，寻找一个最大无交叉子集。
解决
1.建立背包问题的动态规划递归公式。返回值是发f(1,c)的值，利用全局变量profit,weight和numberofobjects。物体价值和重量分别用profit[1:numberofobjects]和weight[1:numberofobjects]来表示。
递归函数：
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个物品装入容量为j的背包中获得的最大价值
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;//获得的最大价值
int w[5] = {2,2,6,5,4};//物品的重量
int v[5] = {6,3,5,4,6};//物品的价值
int x[5];//物品的选取状态
int n = 5;
int C=10;//背包最大容量
s = KnapSack(n, w, v, x, C);
printf("最大物品价值为:\n");
printf("%d\n", s);
system("pause");
return 0;
}
2.所有顶点对之间的最短路径：当边上的权都不是负值的时候，所有顶点对之间的最短路径可以用dijkstra单源算法n次来求解，每一次都选择n个顶点中的一个顶点作为源点。这个过程的时间复杂度为O(n^3)。现采用foly算法，相关的常数因子比Dijkstra算法要小。
假设G中有n个顶点，从1到n编号。c(i,j,k)表示从顶点i到j到一条最短路径的长度，其中间顶点的编号不都大于k。因此，如果边(i,j)存在，则c(i,j,0)是该边的长度。若i=j,则c(i,j,0)为0。如果边(i,j)不存在，则c(i,j,0)等于∞。c(i,j,n)是从i到j的最短路径的长度。
伪代码：
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.网组的无交叉子集：令MNS(i,j)代表一个MNS，其中所有的网组(u,Cu)满足u<=i,Cu<=j。令size(i,j)表示MNS(i,j)的大小。MNS(n,n)是对应于输入实例的一个MNS。
j=C1, size(1,j)=1.
j
j<=Ci, size(i, j)=max{size(i-1,j),size(i-1,Ci-1)+1}
伪代码：(查找网络中最大的无交叉子集)
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;
}
总结
动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。
与分治法不同的是，经动态规划分解得到子问题往往不是互相独立的。如果我们能够保存已解决的子问题的答案，需要时再找出已求得的答案，可避免重复计算，节省时间。可用表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。
适用动态规划的问题必须满足最优化原理和无后效性和子问题的重叠性。
文献引用
《数据结构算法与应用：c++语言描述》
“CSDN博客摘要 ”
《C语言教程》
Jason
18.8.8
