算法3.4完整版

1、 2 动态规划算法动态规划算法 l算法思想 将待求解的问题分解成若干个子问题，并 存储子问题的解而避免计算重复的子问题， 并由子问题的解得到原问题的解。 l动态规划算法通常用于求解具有某种最优 性质的问题。 l动态规划算法的基本要素： 最优子结构性质和重叠子问题。 3 l最优子结构性质：问题的最优解包含着它 的子问题的最优解。即不管前面的策略如 何，此后的决策必须是基于当前状态（由 上一次决策产生）的最优决策。 l重叠子问题：在用递归算法自顶向下解问 题时，每次产生的子问题并不总是新问题， 有些问题被反复计算多次。对每个子问题 只解一次，然后将其解保存起来，以后再 遇到同样的问题时就可以直接引

2、用，不必 重新求解。 4 动态规划动态规划 解决问题的基本特征 1. 动态规划一般解决最值（最优，最 大，最小，最长）问题； 2. 动态规划解决的问题一般是离散 的，可以分解（划分阶段）的； 3. 动态规划解决的问题必须包含最 优子结构，即可以由（n1）的最 优推导出n的最优 5 l动态规划算法的4个步骤： 1. 刻画最优解的结构特性. （一维，二维， 三维数组） 2. 递归的定义最优解. （状态转移方程） 3. 以自底向上的方法来计算最优解. 4. 从计算得到的解来构造一个最优解. 解决问题的基本步骤 6 0-1背包问题：背包问题： 这是最基本的背包问题，特点是：每种物品只有一件， 可以选择

3、放与不放。 当用子问题定义状态时，若fiv表示前i件物品放入一 个容量恰为v的背包中获得的价值最大。可以得到递归方 程为：fiv = max fi-1v, fi-1 v-wi + ai (其中ai 和 wi分别为每个物体的价值和重量) 最后要求fnv的值，因为容量恰为v。其他类型的背 包问题往往也是有0-1背包问题转化而来的。例如采药、 Buy Low，Buy Lower、排队买票问题等。 背包动态规划问题分为三种：背包动态规划问题分为三种： 7 完全背包问题：完全背包问题： 与0-1背包问题类似，所不同的是每件物品有无限件。 递归方程为： fij = max fi-1 j-k*wi + k*

4、ai (k*vi = j) ,在这类问题中，如果当前物品与其它物品相比价值 低，体积大，就可以将其舍弃，这样可以大大减少物品数。 与此同类的问题还有：总分、砝码称重、无限硬币问题等。 多重背包问题：多重背包问题： 与完全背包类似，所不同的是第i种物品可以使用si次， 递归方程： fij = max fi-1 j-k*wi + k*ai (k = si i=n;i+) for(j=1;j=V;j+) if 是0-1背包问题 fij = max fi-1j , fi-1 j-wi + ai if 是完全背包问题 fij = max fi-1 j-k*wi + k*ai (k*wi=j) if 是多

5、重背包问题 fij = max fi-1 j-k*wi + k*ai (k=si for(int j=0; j=jmax; j+) mnj=0; /初始化数组m 15 0-1背包问题背包问题 for(int j = wn;j1;i-) jmax = min(wi-1,c); for(int j=0; jjmax;j+ ) mij = mi+1j ; for(int j = wi; jw1) m1c = max(m1c, m2 c-w1 +v1 ); Void taceback(int *m,int w,int c,int n,int x) for(int i=1;i 时，算法的时间复杂度为O（

6、n* ),这个指数级得时间对于 计算机来说是一个很大的耗费。 由计算m(i,j)的递归式绘制当i=1是的函数图象，如下图示： 2n 17 2n 0-1背包问题背包问题 通过观察发现在变量j是连续的情况下，可以对每一个确定的i，用一个表 pi来存储函数m(i,j)的全部跳跃点。对每一个确定的实数j，可以通过查表 pi来确定函数m(i,j)的值。pi中全部跳跃点（j,m(i,j)依j的值升序排列。 由于函数m(i,j)是关于变量j的阶梯状单调不减函数，故pi中全部跳跃点的 m(i,j)值也是递增排列的。所以可以记录每一个i值的跳跃点，最后通过查找 得出最优解和装载序列。 下面构造不同i值的跳跃点，

7、在构造之前需要明确下面量的含义： （1）函数m(i,j)是由函数m(i+1,j)与函数m(i+1,j-Wi)+Vi做max运算得到 的。因此，函数m(i,j)的跳跃点pi包含于函数m(i+1,j)的跳跃点pi+1与函 数m(i+1,j-Wi)+Vi的跳跃点集qi+1的并集中。其中qi+1=? （2）设(a,b)和(c,d)是pi+1和qi+1并集中的两个跳跃点，则当c=a 且d=1;i-) int k=left; for(int j=left;jc) break; float y=pj0+wi,m=pj1+vi; while(k=right pnext+1=pk+1; if(k=right pnext+1=m; 21 0-1背包问题背包问题 while(k=right while(k=right) pnext0=pk0; pnext+1=pk+1; left=right+1; right=next-1; headi-1=next; traceback(n,w,v,p,head,x); cout跳跃点是：endl; int j=n; for(i=0;inext;i+) cout（pi0,pi1）; if(i=(headj-1) coutendl; j-; 22 0-1背包问题背包问题 return pne