动态规划之01背包讲解.pptVIP

* 3、以自底向上的方式计算出最优值 void KnapSack(int v[],int w[],int c,int n,int m[][11]) { int jMax=min(w[n]-1,c); for (j=0;j=jMax;j++) m[n][j]=0; for (j=w[n];j=c;j++) m[n][j]=v[n]; for (i=n-1;i1;i--) { int jMax=min(w[i]-1,c); for (j=0;j=jMax;j++) m[i][j]=m[i+1][j]; for (j=w[i];j=c;j++) m[i][j]=max(m[i+1][j],m[i+1][j-w[i]]+v[i]); } m[1][c]=m[2][c]; if(c=w[1]) m[1][c]=max(m[1][c],m[2][c-w[1]]+v[1]); } * * 学习要点: 理解动态规划算法的概念。 掌握动态规划算法的基本要素 （1）最优子结构性质 （2）重叠子问题性质 掌握设计动态规划算法的步骤。 (1)找出最优解的性质，并刻划其结构特征。 (2)递归地定义最优值。 (3)以自底向上的方式计算出最优值。 (4)根据计算最优值时得到的信息，构造最优解。 动态规划(DP)Dynamic Programming * 动态规划法的定义：在求解问题中，对于每一步决策，列出各种可能的局部解，再依据某种判定条件，舍弃那些肯定不能得到最优解的局部解，在每一步都经过筛选，以每一步都是最优解来保证全局是最优解。 4.1算法总体思想 动态规划通常应用于最优化问题，即做出一组选择以达到一个最优解。关键是存储子问题的每一个解，以备它重复出现。 * 动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题。 4.1算法总体思想 但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次。 * [问题4-1]：存在一个数字三角形，从顶到底有多条路径， 每一步可沿左斜线向下或垂直向下。路径所经过的数字之和称为路径得分，要求求出最小路径得分。 状态表示1-1 用一元组D（X）描述问题，D（X）表示从顶到达第X层的得分。但是一元组D（X）描述的子问题不能满足最优子结构性质，因为D（X）的最优解可能不包含子问题D（X-I）的最优解。这样，动态规划方法是无法在状态表示1-1上应用。 动态规划对状态表示的要求 * 状态表示 1-2 用二元组D（X，Y）描述问题，D（X，Y）表示到达第X层第Y个位置时的得分，那么 D（X，Y）的最优解包含了子问题D（X+1，Y）或D（X+1，Y-1）的最优解，状态转移方程为 : D（X，Y）= min{D(X+1,Y),D(X+1,Y-1)}+A[X,Y] D（4，*）= A[4,*] * D(i,j) 1 2 3 4 5 6 7 8 1 6 7 2 5 6 6 8 3 6 3 4 5 5 3 4 3 8 1 2 3 8 1 2 D(X，Y)= min {D(X+1，Y),D(X+1,Y-1)} + A[X，Y] * 声明部分； 输入a数组,M行N列；//下标从1开始 for (j = 1; j = N; j++) //O(N) D[M][j]=a[M][j]; for (i = M-1; i =1; i--) //自底向上DP { for (j =M-i+1,n=1; n=2*i; j++,n++) D[i][j]=min(D[i+1][j],D[i+1,j-1])+a[i][j]; } coutmin(D[1]); //输出第一行最小值 } * D(i,j) 1 2 3 4 5 6 7 8 1 1 1 2 3 4 3 4 3 6 5 6 6 6 4 9 13 6 8 9 7 D(X，Y)= min {D(X-1，Y),D(X-1,Y+1)} + A[X，Y] * 4.1算法总体思想 动态规划设计一般要经历以下几个步骤： 1、划分阶段：按照问题的时间或空间特征，把问题分为若干个阶段。 2、确定状态：将问题发展到各个阶段时所处的各种客观情况用不同的状态表示出来。 3、确定决策并写出状态转移方程：因为决策和状态转移有着天然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态，所以如果确定了决策，状态转移方程也就可以写出。 4、寻找边界条件：给出的状态转移方程是一个递推式，需要一个递推的终止条件或边界条件。 5、程