参考书籍：算法设计与分析——C++语言描述（第二版）
二叉搜索树运算有很好的平均时间复杂度（。
以上分析均假定二叉搜索树上搜索一个元素的概率是相等的。如果元素集合是固定的，并且已知搜索集合中每个元素的概率，包括不成功的概率，那么可以构造一颗最优二叉搜索树，使其具有最小的平均搜索时间。
设有元素集合）。显然：
最优二叉搜索树问题是指设法构造一颗具有最小平均搜索时间的二叉搜索树。
已知递增有序的元素集合的左子树和右子树，它们应当都是最优二叉搜索树。
与二分搜索的二叉判定树类似，每个内结点代表一次成功搜索可能的终止位置，每个外结点表示一次成功搜索可能的终止位置，每个外结点表示一次不成功搜索的终止位置。设
假定
定义
设
设w、c和r是上面定义的3个二维数组，计算此3个量，便可以从中得到最优二叉搜索树。运用动态规划法求解这三个量的递推算法如下：
计算主对角线的w、c和r的值
计算紧邻主对角线上面的那条对角线的w、c和r的值
根据下列公式，计算主对角线以上n-2条斜线的w、c和r的值
一维数组p和q保存成功和不成功搜索的两种概率，n是数组长度，计算结果保存在二维数组w、c和r的值。函数Find计算满足的k值。函数CreateOBST调用Find计算w、c和r。最后根据r的值可以构造所求得的最优二叉搜索树。
//构造最优二叉搜索树
int Find(int i,int j,int **r,float **c)
{
float min=INFTY;
int k;
for(int m = i+1;m<=j;m++){
if((c[i][m-1]+c[m][j])<min){
min=c[i][m-1]+c[m][j];
k=m;
}
}
return k;
}
void CreateOBST(float *p,float *q,float **c,int **r,float **w,int n)
{
for(int i=0;i<=n-1;i++){
//初始化
w[i][i]=q[i];c[i][i]=0.0;r[i][i]=0;
w[i][i+1]=q[i]+q[i+1]+p[i+1];
c[i][i+1]=q[i]+q[i+1]+p[i+1];
r[i][i+1]=i+1;
}
w[n][n]=q[n];c[n][n]=0.0;r[n][n]=0;
for(int m = 2;m<=n;m++){
//计算n-2条对角线元素
for(i=0;i<=n-m;i++){
int j = i+m;
w[i][j]=w[i][j-1]+p[j]+q[j];
int k=Find(i,j,r,c);
c[i][j]=w[i][j]+c[i][k-1]+c[k][j];
r[i][j]=k;
}
}
}Find函数用于计算k，其计算时间为
与使用贪心法求解的一般背包问题不同，在0/1背包问题中，物品不能分割只能作为一个整体或者装入或者不装入背包。
0/1背包问题可以描述为：已知一个载重为M的背包和n件物品，物品编号为。在物品不能分割、只能整件装入背包的情况下，求一种最佳装载方案使得总收益最大。
0/1背包问题可以形式化为：给定最大。不妨使用KNAP(0,n-1,M)表示一个背包问题的实例。
判断一个问题是否适用于动态规划法求解，首先必须分析问题解的结构，考察它的最优解是否具有最优子结构特性。其次应当检查分解所得的子问题是否相互独立，是否存在重叠子问题现象。
0/1背包的最优解具有最优子结构特性。设
给定一个0/1背包问题实例KNAP(0,n-1,M)，可以通过对n个物品是否加入背包做出一系列决策进行求解，假定变量做出决策后，存在两种情况：
设
//0/1背包的递归算法
template<class T>
class Knapsack
{
public:
Knapsack(int mSize,float cap,float *wei,T *prof);
T RKnap();
private:
T f(int j,float X);//递归函数f计算0/1背包的最大收益
float m,*w;
T *p;
int n;
};
template<class T>
T Knapsack<T>::f(int j,float X)
{
if(j<0)
return ((X<0)? -INFTY:0);
if(X<w[j])
return f(j-1,X);
else {
T a=f(j-1,X);
T b=f(j-1,X-w[j])+p[j];
if(a>b)
return a;
else
return b;
}
}
template<class T>
T Knapsack<T>::RKnap()
{
if(n>0)
return f(n-1,m);
else
return NoAns;//NoAns可定义为类型T的一个代表无收益的常量
}上述0/1背包递归算法的时间复杂度在最坏情况下是指数级的（）。
如果X是满足，其中M是背包载重量，n是物品个数。
但是如果物品重量和背包载重为实数，那么子问题的最优解值的连续函数，上述方法就无法解决问题，只能开发物品重量为 实数的0/1背包的动态规划算法。
0/1背包问题的图解法
用
计算所有的步骤如下：
设所支配。
通过回溯方式，可以求得0/1背包的最优解，