复制成功
  • 图案背景
  • 纯色背景

笔记

  • 2019-11-16
    为大人带来形象的羊生肖故事来历 为孩子带去快乐的生肖图画故事阅读
    谈谈怎样学好数学_苏步青-中学生文库
poormann

上传于:2014-03-03

粉丝量:89

该文档贡献者很忙,什么也没留下。



算法第4章-第6讲-动态规划(1)

下载积分:1000

内容提示: 每节一经典规划是全面的长远的发展计划第6讲 动态规划计算机科学学院 王 小明(博士/教授/博士生导师)Email: wangxm@snnu. edu. cn 算法总体思想算法总体思想动态规划算法与分治法类似, 其基本思想也是将待求解问题分解成若干个子问题第6讲 动态规划nT(n/2)T(n/2)T(n/2)T(n/2)T(n)= 与分治法不同之处在于, 子问题往往不是互相独立的。在用分治法求解时, 有些子问题被重复计算许多次,将会导致算法具有较大的时间复杂度。如果能够保存已解决的子问题的答案, 而在需要时再找出已求得的答案, 就可以避免大量重复计算, 从而得到多项式时间算法这个策略就是动态规...

文档格式:PPT| 浏览次数:128| 上传日期:2014-03-03 16:02:32| 文档星级:
每节一经典规划是全面的长远的发展计划第6讲 动态规划计算机科学学院 王 小明(博士/教授/博士生导师)Email: wangxm@snnu. edu. cn 算法总体思想算法总体思想动态规划算法与分治法类似, 其基本思想也是将待求解问题分解成若干个子问题第6讲 动态规划nT(n/2)T(n/2)T(n/2)T(n/2)T(n)= 与分治法不同之处在于, 子问题往往不是互相独立的。在用分治法求解时, 有些子问题被重复计算许多次,将会导致算法具有较大的时间复杂度。如果能够保存已解决的子问题的答案, 而在需要时再找出已求得的答案, 就可以避免大量重复计算, 从而得到多项式时间算法这个策略就是动态规划得到多项式时间算法。 这个策略就是动态规划。第6讲 动态规划n=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2n/2T(n/4)T(n/4)n/2T(n/4) T(n/4)T(n/4)T(n/4) T(n/4)T(n) 第6讲 动态规划在动态规划算法策略中, 它的决策不是线性的而是全面考虑不同的情况分别进行决策, 并通过多阶段决策来最终解决问题。 在各个阶段采取决策后, 会不断决策出新的数据, 直到找到最优解.每次决策依赖于当前状态, 又随即引起状态的转移. 一个决策序列就是在变化的状态中产生出来的,故有“动态” 的含义。 我们把这种通过多阶段决策以最优化解决问题的过程称为动态规划。 第6讲 动态规划认识动态规划我们通过一个简单的例子来说明动态规划的多阶段决策与贪婪算法有什么区别。婪例题15: 数塔问题1018285991512671941016 第6讲 动态规划数塔问题如图所示的一个数塔, 从顶部出发, 在每一结点可以选择向左走或是向右走, 一直走到底层, 要求找出一条路径, 使路径上的数值和最大。问题分析算法设计算法小结1018285991512671941016 第6讲 动态规划这个问题用贪婪算法有可能会找不到真正的最大和。以图为例就是如此. 用贪婪的策略, 则路径和分别为:自上而下:自下而上:问题分析101018182288559999151512126677191944101016169+15+8+9+10=5119+2+10+12+9=5210101818228855999915151212667719194410101616 第6讲 动态规划问题分析事实上, 贪婪选择得不到最优解, 通过观察真正的最大和是:9+12+10+18+10=59在知道数塔的全貌的前提下, 可以用枚举法或下一章将学习的图搜索算法来完成。下来看动态规划如何解决这个问题?1018285991512671941016 第6讲 动态规划方法1: 自底向上用“动态规划” 选择91512504959101828596719410161921281921383429710416 第6讲 动态规划以上的决策结果将五阶数塔问题变为4阶子问题,递推出第四层与第五层的和为:21 (2+1 9) , 28(18+1 0) , 1 9(9+1 0) , 21(5+1 6) 。() ,(用同样的方法还可以将4阶数塔问题, 变为3阶数塔问题。…… 最后得到的1 阶数塔问题, 就是整个问题的最优解。方法1: 自底向上用“动态规划” 选择阶段划分) ,() ,()1018285991512671941016 第6讲 动态规划自下而上逐层决策过程:第一步对于第五层的数据, 我们做如下4次决策:对经过第四层2的路径选择第五层的19,对经过第四层1 8的路径选择第五层的1 0对经过第四层1 8的路径选择第五层的1 0,对经过第四层9的路径也选择第五层的1 0,对经过第四层5的路径选择第五层的16。阶段划分: 第6讲 动态规划方法1: 自底向上用“动态规划” 选择91512504959101828596719410161921281921383429710416 第6讲 动态规划方法2: 自顶向向用“动态规划” 选择如何选择?915122124910182859671941016523349413731303256594543 第6讲 动态规划2. 数据结构设计1) 原始信息存储原始信息包括层数和数塔中的数据,层数用一个整型变量n存储,数塔中的数据数塔中的数据用二维数组data,存储成如下的下三角阵:912 1510 6 82 18 9 519 7 10 4 16维数1018285991512671941016 2) 动态规划过程存储用维数组 存储各阶段的决策结果用二维数组d存储各阶段的决策结果。 二维数组d的存储内容如下(n: 行, j: 列) :step1 d[n][j]=data[n][j] //最低层元素, j=1,2,……,n;step2 for i=n-1 to 1for j=1 to id[i][j]=max(d[i+1][j], d[i+1][j+1])+data[i][j]最后d[1][1]存储的就是问题的结果。维数组10182859915126719410161921281921383429504959710416 第6讲 动态规划数组data 数组d9 59 12 15 50 4910 6 8 38 34 292 18 9 5 21 28 19 2119 7 10 4 16 19 7 10 4 16最后d[1][1]存储的就是问题的结果。d[1][1] ; n=1 第6讲 动态规划自顶向下找路径: 使用数组data和数组d自顶向下找路径, 可以找到最优解的路径。 求解和输出过程如图所示:所示3) 最优解路径求解及存储数组data 数组d9 59 12 15 50 4910 6 8 38 34 292 18 9 5 21 28 19 2119 7 10 4 16 19 7 10 4 161010数塔及动态规划过程数据59-9=5050-12=3838-10=2828-18=109121018 第6讲 动态规划step1: 输出d[1][1]对应的data[1][1]: "9"b=d[1][1]-data[1][1]=59-9=50, b与“9”的下方数据d[2][1],d[2][2] 比较: b与d[2][1]相等, 输出已知最大值d[1][1], 自顶向下找路径算法描述:data[2][1]: "12"step2:b=d[2][1]-data[2][1]=50-12=38, b与d[3][1]和d[3][2] 比较: b与d[3][1]相等, 输出data[3][1]: "10"step3:b=d[3][1]-data[3][1]=38-10=28, b与d[4][1]和d[4][2] 比较, b与d[4][2]相等, 输出data[4][2]: "18"step4:b=d[4][2]-data[4][2]=28-18=10,b与d[5][2]和d[5][3] 比较, b与d[5][3]相等, 输出data[5][3]: "10 " 第6讲 动态规划为了提高算法的时间效率, 在动态选择的过程中, 同时记录每一步选择数据的方向, 这就又需要一组二维数组。为了设计简洁的算法我们最后用三维数组为了设计简洁的算法, 我们最后用三维数组a[50][50][3]存储以上确定的三个数组的信息。a[50][50][1]代替数组data,a[50][50][2]代替数组d, a[50][50][3]为解路径标记(0:向下, 1:向右下)。其中: a[50][50][3]=0表示向“下” 走,a[50][50][3]=1表示向“右下” 走算法优化912 1510 6 82 18 9 519 7 10 4 16 第6讲 动态规划数塔问题的算法main( ) { int a[50][50][3],i,j,n; //定义一个三维数组print( ‘please input the number of rows:’);//输入行数input(n);input(n);for( i=1 ;i<=n;i++)for j=1 to i do{ input(a[i][j][1]);// 输入从塔顶到塔底所对应的数字a[i][j][2]=a[i][j][1];//再复制一组数据到另 一个数组, 用 来存放数据当前的最优a[i][j][3]=0;} // 给数组3赋值0, 用 来记录路径初始化 第6讲 动态规划for (i=n-1 ; i>=1;i--)//从塔底的上一层开始寻找路径for (j=1 ;j>= i ;j++)if (a[i+1][j][2]>a[i+1][j+1][2]) { a[i][j][2]=a[i][j][2]+a[i+1][j][2]a[i][j][3]=0;} //表示向下走else{[i][j][2][i][j][2]{ a[i][j][2]=a[i][j][2]+a[i+1][j+1][2] ];a[i][j][3]=1} //表示向右下方走[i 1][j 1][2] ]找最大指的同时找找路径print(‘max=’,a[1][1][2]);//输出最大值j=1;for( i=1 ;i<= n-1;i++)//输出 最优路径{ print(a[i][j][1],‘->’);j=j+a[i][j][3]; }print (a[n][j][1]);}输出路径上的数据 第6讲 动态规划从例子中可以看到:动态规划=贪婪策略+递推(降阶) +存储递推结果贪婪策略、 递推算法都是“线性” 地解决问题, 而贪婪策略、 递推算法都是线性地解决问题, 而动态规划则是全面分阶段地解决问题。 可以通俗地说动态规划是“带决策的多阶段、 多方位的递推算法” 。 第6讲 动态规划1. 适合动态规划的问题特征适合用动态规划算法解决的问题及决策应该具有三个性质:算法框架最优化原理、 无后向性、 子问题重叠性质:a) 最优化原理(或称为最佳原则、 最优子结构) 。b) 无后向性(无后效性) 。c) 有重叠子问题。 (子问题之间是不独立的) 第6讲 动态规划2. 动态规划的基本思想动态规划方法的基本思想是, 把求解的问题分成许多阶段或多个子问题, 然后按顺序求解各子问成许多阶段或多个子问题, 然后按顺序求解各子问题。 最后一个子问题的解就是初始问题的解。算法框架由于用动态规划所解的问题有重叠子问题特点,为了减少重复计算, 对每一个子问题只解一次, 将其不同阶段的不同状态保存在一个二维数组中。 第6讲 动态规划设计一个标准的动态规划算法的步骤:1 ) 划分阶段2) 选择状态3) 确定决策并写出状态转移方程3) 确定决策并写出状态转移方程实际应用当中的简化步骤:1 ) 分析最优解的性质, 并刻划其结构特征。2) 递推地定义最优值。3) 以自底向上的方式或自顶向下的记忆化方法(备忘录法) 计算出最优值.4) 根据计算最优值时得到的信息, 构造问题的最优解。3. 设计动态规划算法的基本步骤 第6讲 动态规划for( j=1 ;j<=m;j=j+1)//第一个阶段xn[j]=初始值;for (i=n-1 ; i>=1;i=i-1) //其它n-1 个阶段for (j=1 ;j<=f(i) ;j=j+1) // f(i ) 与 i 有关的表达式4. 标准动态规划的基本框架初始化最优值(状态值)xi[j]=j=max(或min){g(xi-1[j1: j2]),… g(xi-1[jk: jk+1] ) } ; //表示xi[j]与xi-1[j1]-xi-1[j2],… xi-1[jk]-xi-1[jk+1]有关, 取它们最大或者最小。t=g(x1[j1: j2]); //由最优值求解最优解的方案print(x1[j1]); //输出最优值for( i=2 ;i<= n-1;i=i+1) //输出最优解的路径{t=t-xi-1[ji];for (j=1 ;j<=f(i) ;j=j+1) if(t=xi[ji]) break;}输出最优解 第6讲 动态规划最短路径选择问题从师大长安校区到雁塔校区可以经过下图中的路径到达, 从中选择一条全程距离最短的路径。1622AA1A2长安校区校区长安长安校区雁塔校区533687683533842123335526643B1B2C2D2A3B3C3A4B4C4A5B5 第6讲 动态规划最短路径选择问题从师大长安校区到雁塔校区可以经过下图中的路径到达, 从中选择一条全程距离最短的路径。1622A11313A21313AA37AA47长安校区校区18长安长安校区雁塔校区533687683533842123335526643B116B210C29D212B36C38B45C49A54B53 第6讲 动态规划最短路径选择问题从师大长安校区到雁塔校区可以经过下图中的路径到达, 从中选择一条全程距离最短的路径。1622A11313A21313AA37AA47长安校区校区18长安长安校区雁塔校区533687683533842123335526643B116B210C29D212B36C38B45C49A54B53 第6讲 动态规划求图中任意两点之间的最短路径选择问题从师大长安校区到雁塔校区可以经过下图中的路径到达, 从中选择一条全程距离最短的路径。1622A11313A21313AA37AA47长安校区校区18长安长安校区A0雁塔校区533687683533842123335526643B116B210C29D212B36C38B45C49A54B53B0 第6讲 动态规划求图中任意两点之间的最短路径选择问题A0A1B1A2B2 C2D2A3B3C3A4 B4C4A5 B5B0A0.99 530…..B0设邻接矩阵为: D={di,j}nxn,则图中任意两点之间的最短路算法如下: 第6讲 动态规划求图中任意两点之间的最短路径选择问题实际需要计算D(2) =DxD, D(3)= D(2)xD, …, D(n)=D(n-1)xD.Step 1. D’←D 复制D为D’Step 2. For k=1 to nfor i=1 to nfor i=1 to nfor j=1 to nd(i,j)←min{d(i,j), d(i,k)+d(k,j)}} }}Step 3. End同学们先手工求解例题中的D(17), 然后计算机实验上述算法。 第6讲 动态规划0-1背包问题 给定n种物品和一背包。 物品i 的重量是wi, 其价值为bi, 背包的容量为W。 问应如何选择装入背包的物品, 使得装入背包中物品的总价值最大? 其中, 物品i 要么整体装入, 要么整体不装入, 不可分一部分装入, (wi, bi和 W 都是整数)整体不装入不可分部分装入(b 和 W 都是整数) 0-1背包问题是一个特殊的整数规划问题。iniixb1maxi1 , 0 {nixWxwinii1},1 第6讲 动态规划0-1背包问题背包最大容量:W=20¥10¥10Bag 1¥32kg背包20kg¥8¥5¥43kg4kg5kg9kgMax wBag 2Bag 4Bag 3Bag 5 第6讲 动态规划0-1背包枚举法 n个物品, 有2n种可能的组合. (选择或者不选择) 对每个组合, 计算其价值和重量; 从中选出 对每个组合, 计算其价值和重量; 从中选出重量不超过W , 并且价值最大的组合. 算法的时间复杂度为 O(2n) , 指数级复杂度! 第6讲 动态规划0-1背包子问题的定义 设n个物品用1,…,n表示, 可以定义子问题如下: 对S = {1k} 即k个物品下: 对Sk= {1, …, k},即k个物品, 求最优解.求最优解 这当然是一个合法的子问题, 但是, 我们能用Sk的解描述Sn的解么?  十分不幸, 我们不能. 原因…. ? ? 第6讲 动态规划0-1背包这当然是一个合法的子问题, 但是, 我们能用Sk的最优解描述Sn的最优解么? S1S2S3S4S5通过一个“不能” 描述的例子说明上述方法不可行。 第6讲 动态规划0-1背包当k=4时:对于S4:放入的物体的重量: 1 4放入的物体的价值: 20当k=5时, 以下S5是不包括S4的子问题之一w1 =2b1 =3w2 =3b2 =4w3 =4b3 =5w4 =5b4 =8wibi4332重量价值包编号12S4S5S5??1 0855494354对于S5:放入的物体的重量: 20放入的物体的价值: 26S4的解不是S5的解的一部分! ! !w1 =2b1 =3w3 =4b3 =5w4=5b4 =8w5 =9b5=10 第6讲 动态规划0-1背包 如上所述, S5的最优解不能用S4的最优解表示 上面的子问题定义是错误的, 必须重新定义!子问题的正确定义 我们增加另外一个参数: w, 它表示放入背包的物品的总重量. 定义B[k, w] 为可放入背包的, 编号不超过k, 总重量不超过w 的物品的最大价值. 第6讲 动态规划0-1背包用动态规划方法解0-1背包问题其动态规划方程如下: wif ]], 1[[]][[kkwwkBkkBBotherwise }], 1[],, 1[max{,,kkbwwkBwkBw定义B[k,w] 为可放入背包的, 编号不超过k, 总重量不超过w的物品的最大价值. 第6讲 动态规划0-1背包算法设计Knapsack(int n, b[],w[],W){boolean x[]; // x[i]=1 :物品 i 放入背包for (int w = 0; w<=W; w++) B[0,w] = 0;for (int i = 1 ; i<=n; i++) {B[i 0] = 0;B[i,0] 0;for (int w = 0; w<=W; w++){if (w[i] <= w){// 物品i可以放入背包if (b[i] + B[i-1 ,w-w[i] ]> B[i-1 ,w])初始化then {B[i,w] = b[i] + B[i-1 ,w- w[i]];x[i]=1 ;}{B[i,w] = B[i-1 ,w]; x[i]=0;}else}else {B[i,w] = B[i-1 ,w]; x[i]=0;} // 从头顶下来}}}寻找最优值 for w = 0 to WB[0,w] = 0for i = 1 to nfor i 1 to nB[i,0] = 0for w = 1 to W< 代码的其余部分 >所以算法时间复杂度是: O(n*W)注: 枚举法的时间复杂度为 O(2n)第6讲 动态规划0-1背包时间复杂度O(W)循环 n 次循环 n 次循环W次 第6讲 动态规划0-1背包用上述算法计算下面的实例:最大容量W=5的背包Bag 1¥32kg背包5kg¥6¥5¥43kg4kg5kg9kgMax wBag 2Bag 4Bag 3 第6讲 动态规划0-1背包000000w01235i0140B[i,w]:for w = 0 to WB[0,w] = 0423for i = 1 to nB[i,0] = 0000先填行:再填列: 第6讲 动态规划0-1背包000000w 01235i012400i :(wi,bi)1: (2 ,3)2: (3 ,4)3: (4 ,5) ( , )4: (5 ,6)0物品if wi≤ w if bi+ B[i-1,w-wi] > B[i-1,w] then B[i,w] = bi+ B[i-1,w- wi]else B[i,w] = B[i-1,w]else B[i,w] = B[i-1,w] // wi> w 4300w-wi=-1w 第6讲 动态规划0-1背包000000w 01235i012400i :(wi,bi)1: (2 ,3)2: (3 ,4)3: (4 ,5) ( , )4: (5 ,6)物品物品03if wi≤ wif bi+ B[i-1,w-wi] > B[i-1,w]else B[i,w] = B[i-1,w]else B[i,w] = B[i-1,w] // wi> w B[i,w] = bi+ B[i-1,w- wi]4300w-wi=0w 第6讲 动态规划0-1背包000000w 01235i012400i :(wi,bi)1: (2 ,3)2: (3 ,4)3: (4 ,5) ( , )4: (5 ,6)物品033wif wi≤ wif bi+ B[i-1,w-wi] > B[i-1,w]else B[i,w] = B[i-1,w]else B[i,w] = B[i-1,w] // wi> w B[i,w] = bi+ B[i-1,w- wi]4300w-wi=1 第6讲 动态规划0-1背包000000w 01235i012400i :(wi,bi)1: (2 ,3)2: (3 ,4)3: (4 ,5) ( , )4: (5 ,6)物品w0333if wi≤ wif bi+ B[i-1,w-wi] > B[i-1,w]else B[i,w] = B[i-1,w]else B[i,w] = B[i-1,w] // wi> w B[i,w] = bi+ B[i-1,w- wi]4300w-wi=2 第6讲 动态规划0-1背包w0300000w 01235i012400i :(wi,bi)1: (2 ,3)2: (3 ,4)3: (4 ,5) ( , )4: (5 ,6)物品0333if wi≤ wif bi+ B[i-1,w-wi] > B[i-1,w]else B[i,w] = B[i-1,w]else B[i,w] = B[i-1,w] // wi> w B[i,w] = bi+ B[i-1,w- wi]4300w-wi=3 第6讲 动态规划0-1背包0300000w 01235i012400i :(wi,bi)1: (2 ,3)2: (3 ,4)3: (4 ,5) ( , )4: (5 ,6)物品物品03330if wi≤ w if bi+ B[i-1,w-wi] > B[i-1,w] B[i,w] = bi+ B[i-1,w- wi]else B[i,w] = B[i-1,w]else B[i,w] = B[i-1,w] // wi> w 4300w-wi=-2w 第6讲 动态规划0-1背包0300000w 01235i012400i :(wi,bi)1: (2 ,3)2: (3 ,4)3: (4 ,5) ( , )4: (5 ,6)物品033303if wi≤ w if bi+ B[i-1,w-wi] > B[i-1,w] B[i,w] = bi+ B[i-1,w- wi]else B[i,w] = B[i-1,w]else B[i,w] = B[i-1,w] // wi> w 4300w-wi=-1w 第6讲 动态规划0-1背包0300000w 01235i012400i :(wi,bi)1: (2 ,3)2: (3 ,4)3: (4 ,5) ( , )4: (5 ,6)物品0334303wif wi≤ wif bi+ B[i-1,w-wi] > B[i-1,w]else B[i,w] = B[i-1,w]else B[i,w] = B[i-1,w] // wi> w B[i,w] = bi+ B[i-1,w- wi]4300w-wi=0 第6讲 动态规划0-1背包0300000w 01235i012400i :(wi,bi)1: (2 ,3)2: (3 ,4)3: (4 ,5) ( , )4: (5 ,6)物品w03330344if wi≤ wif bi+ B[i-1,w-wi] > B[i-1,w]else B[i,w] = B[i-1,w]else B[i,w] = B[i-1,w] // wi> w B[i,w] = bi+ B[i-1,w- wi]4300w-wi=1 第6讲 动态规划0-1背包w0300000w 01235i012400i :(wi,bi)1: (2 ,3)2: (3 ,4)3: (4 ,5) ( , )4: (5 ,6)物品033303447if wi≤ w if bi+ B[i-1,w-wi] > B[i-1,w]else B[i,w] = B[i-1,w]else B[i,w] = B[i-1,w] // wi> w B[i,w] = bi+ B[i-1,w- wi]4300w-wi=2 第6讲 动态规划0-1背包0300000w 01235i012400i :(wi,bi)1: (2 ,3)2: (3 ,4)3: (4 ,5) ( , )4: (5 ,6)物品033303447if wi≤ wif bi+ B[i-1,w-wi] > B[i-1,w] B[i,w] = bi+ B[i-1,w- wi]else B[i,w] = B[i-1,w]else B[i,w] = B[i-1,w] // wi> w 4300w-wi<0 i=1,2,3034 第6讲 动态规划0-1背包0300000w 01235i012400i :(wi,bi)1: (2 ,3)2: (3 ,4)3: (4 ,5) ( , )4: (5 ,6)物品033303447if wi≤ w if bi+ B[i-1,w-wi] > B[i-1,w]else B[i,w] = B[i-1,w]else B[i,w] = B[i-1,w] // wi> w B[i,w] = bi+ B[i-1,w- wi]4300w-wi=00345 第6讲 动态规划0-1背包0300000w 01235i012400i :(wi,bi)1: (2 ,3)2: (3 ,4)3: (4 ,5) ( , )4: (5 ,6)物品033303447if wi≤ w if bi+ B[i-1,w-wi] > B[i-1,w] B[i,w] = bi+ B[i-1,w- wi]else B[i,w] = B[i-1,w]else B[i,w] = B[i-1,w] // wi> w 4300w-wi=103457 第6讲 动态规划0-1背包0300000w 01235i012400i :(wi,bi)1: (2 ,3)2: (3 ,4)3: (4 ,5) ( , )4: (5 ,6)物品033303447if wi≤ w if bi+ B[i-1,w-wi] > B[i-1,w] B[i,w] = bi+ B[i-1,w- wi]else B[i,w] = B[i-1,w]else B[i,w] = B[i-1,w] // wi> w 4300w-wi<0 i=1,2,3,4034570345 第6讲 动态规划0-1背包0300000w 01235i012400i :(wi,bi)1: (2 ,3)2: (3 ,4)3: (4 ,5) ( , )4: (5 ,6)物品033303447if wi≤ w if bi+ B[i-1,w-wi] > B[i-1,w]else B[i,w] = B[i-1,w]else B[i,w] = B[i-1,w] // wi> w B[i,w] = bi+ B[i-1,w- wi]4300w-wi=10345703457 第6讲 动态规划0-1背包03000000w 01235i012400i :(wi,bi)1: (2 ,3)2: (3 ,4)3: (4 ,5) ( , )4: (5 ,6)物品03333034477774300034503457 7所以: 选择包1 和包2可以使得背包价值最大b1+b2=7 第6讲 动态规划0-1背包算法分析 整个算法都是针对n个物品× W(包最大重量) 进行运算的, 所以时间复杂度为O(n× W) 此算法效率虽然较高, 但它只能针对”整数” 重量的背包问题问题。例如: n=3,W=10; 对非整数重量w={3.14,5,9.6},b ={5,7,10}重量扩大100倍, 转化为:n=3,W=1000,w={314,500,960},b={5,7,10} 需要开辟1000个空间(包容量) , 计算接近1000次。时间、 空间效率较低。 这样用动态规划就不合适了。例如: 第6讲 动态规划0-1背包算法分析背包的容量: 30kg三个物品的重量和价值:•包1 : 5kg,包•包2: 1 0kg,•包3: 20kg,¥50¥60¥1 40¥140g5 kg¥5010 kg¥60220kg330kgMax.背包1需要开辟3×30的矩阵效率不如观察法较简单 第6讲 动态规划从例子中可以看到:动态规划=贪婪策略+递推(降阶) +存储递推结果贪婪策略、 递推算法都是“线性” 地解决问题, 而贪婪策略、 递推算法都是线性地解决问题, 而动态规划则是全面分阶段地解决问题。 可以通俗地说动态规划是“带决策的多阶段、 多方位的递推算法” 。 第6讲 动态规划1. 适合动态规划的问题特征适合用动态规划算法解决的问题及决策应该具有三个性质:算法框架最优化原理、 无后向性、 子问题重叠性质:a) 最优化原理(或称为最佳原则、 最优子结构) 。b) 无后向性(无后效性) 。c) 有重叠子问题。 (子问题之间是不独立的) 第6讲 动态规划2. 动态规划的基本思想动态规划方法的基本思想是, 把求解的问题分成许多阶段或多个子问题, 然后按顺序求解各子问成许多阶段或多个子问题, 然后按顺序求解各子问题。 最后一个子问题的解就是初始问题的解。算法框架由于用动态规划所解的问题有重叠子问题特点,为了减少重复计算, 对每一个子问题只解一次, 将其不同阶段的不同状态保存在一个二维数组中。 第6讲 动态规划设计一个标准的动态规划算法的步骤:1 ) 划分阶段2) 选择状态3) 确定决策并写出状态转移方程3) 确定决策并写出状态转移方程实际应用当中的简化步骤:1 ) 分析最优解的性质, 并刻划其结构特征。2) 递推地定义最优值。3) 以自底向上的方式或自顶向下的记忆化方法(备忘录法) 计算出最优值.4) 根据计算最优值时得到的信息, 构造问题的最优解。3. 设计动态规划算法的基本步骤 第6讲 动态规划for( j=1 ;j<=m;j=j+1)//第一个阶段xn[j]=初始值;for (i=n-1 ; i>=1;i=i-1) //其它n-1 个阶段for (j=1 ;j<=f(i) ;j=j+1) // f(i ) 与 i 有关的表达式4. 标准动态规划的基本框架初始化最优值(状态值)xi[j]=j=max(或min){g(xi-1[j1: j2]),… g(xi-1[jk: jk+1] ) } ; //表示xi[j]与xi-1[j1]-xi-1[j2],… xi-1[jk]-xi-1[jk+1]有关, 取它们最大或者最小。t=g(x1[j1: j2]); //由最优值求解最优解的方案print(x1[j1]); //输出最优值for( i=2 ;i<= n-1;i=i+1) //输出最优解的路径{t=t-xi-1[ji];for (j=1 ;j<=f(i) ;j=j+1) if(t=xi[ji]) break;}输出最优解 第6讲 动态规划突出阶段性的动态规划应用例题1 7:例题1 7:资源分配问题资源分配问题 第6讲 动态规划设有资源n(n为整数) , 分配给m个项目 , gi(x) 为第i 个项目 分得资源x(x为整数) 所得到的利润。 求总利润最大的资源分配方案, 也就是解下列问题:= ( ) +( ) +max z=g1(x1) + g2(x2) +……gm(xm)x1+x2+x3+……xm=n, 0≤xi≤n, i =1 , 2, 3, …, m函数gi(x) 以数据表的形式给出.( )例1 7: 资源分配问题 例如: 现有7万元投资到A, B, C 三个项目, 利润见表。需要求解的问题: 总利润最大的资源分配方案。例1 7: 资源分配问题第6讲 动态规划 第6讲 动态规划1. 阶段划分及决策比较直观的阶段划分就是逐步考虑每一个项目 在不同投资额下的利润情况。 每个阶段要考虑各种分配方案下的最大利润, 设fi(x) 为将资源x分配给前i 个项目案下的最大利润, 设fi(x) 为将资源x分配给前i 个项目所获得的最大利润, gi(x)为第i个项目分得资源x所得到的利润。 分阶段决策过程:f1(x) =g1(x)0≤x≤ nfi(x) =max{gi(x) +fi -1(n-x) } 0≤x≤ n,i=2,3,…n由于每一阶段都考虑了所有的投资情况, 所以算法策略是满足最佳原理的。算法设计 第6讲 动态规划2. 实例1. 考虑分配给第一个项目A的资金x与利润f1(x) 的关系算法设计项目A的资金与利润表0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 0.11 0.1 3 0.1 5 0.21 0.24 0.30 0.350 0.11 0.13 0.15 0.21 0.24 0.30 0.35xxff1(x)f1(x)2.考虑分配给前两个项目A, B的总资金x( 0≤x≤ n )与利润f2(x)的关系, x2 为分配给项目B的资金.f 第6讲 动态规划算法设计项目A、 B的资金与利润表2.考虑分配给前两个项目A,B的总资金x(0≤x≤ n )资金x与利润f2(x)的关系,x2 为分配给项目B的资金0011223344556677f (x)f2(x)0.12x2x2其中带”×”号的数据为当前最大获利10.11 0.12×0.13 0.23×0.15 0.25 0.27×0.21 0.27 0.29 0.32 ×0.24 0.33 0.31 0.34×0.340.30 0.36 0.37×0.35 0.42×0.42 20.16 0.2330.21 0.2740.23 0.3250.34×0.25 60.36 0.36 0.36 0.24 0.3770.40 0.42×0.38 0.38 0.35 0.34 x 第6讲 动态规划0 1 2 3 4 5 6 7 ++xff1(x)项目A、 B的资金与利润表计算过程01234567f2(x)0.1212345670.11 0.12×0.13 0.23×0.15 0.25 0.27×0.21 0.27 0.29 0.32 ×0.24 0.33 0.31 0.34×0.30 0.36 0.37×0.35 0.42×0.16 0.230.21 0.270.23 0.320.34×0.36 0.36 0.36 0.24 0.370.40 0.42×0.38 0.38 0.35 0.34 0.42 0.25 0.34x2x0 0.11 0.13 0.15 0.21 0.24 0.30 0.35 第6讲 动态规划算法设计项目A、 B 、 C的资金与利润表项目A、 B 、 C的资金与利润表3.最后只需考虑投入7万元资金给A,B,C 3个项目,资金,利润的关系: f3(7)=max{g3(x3)+f2(7-x3)},其中0 分配给项目C的资金≤ x3≤7为x301234567g3(x3)0.00 0.08 0.12 0.20 0.24 0.26 0.30 0.35f2(7-x3)0.42 0.37 0.34 0.32 0.27 0.23 0.12 0.00 g3(x3)+f2(7-x3)0.42 0.45 0.46 0.52×0.350.51 0.49 0.42 其中带”×”号的数据为当前最大获利所以f3(7)=max{g3(x3)+f2(7-x3)}=g3(3)+f2(4)=0.52 第6讲 动态规划3. 数据结构设计:1) 开辟一维数组q来存储原始数据。2) 另开辟一维数组f存储当前最大收益情况。3) 开辟记录中间结果的一维数组temp, 记录3) 开辟记录中间结果的算法设计维数组temp, 记录正在计算的最大收益。4) 开辟二维数组a, 保存前i 个工程投资j(万元) 获得最大利润时, 给第i 个工程分配的资源数。5) 数组gai n存储第i 个工程投资数的最后结果。 第6讲 动态规划对于一般问题设计算法如下:main( ) { int i,j,k,m,n,rest; int a[100][100], gain[100];//初始化过程float q[100],f[100],temp[100];print(“How mang item? ”); input (m);//输入项目 数print(“How mang money? ”); input (n);//输入投入资金额print(“input gain table:”);//输出第一个项目 最大利益for( j=0;j<= n;j++){ input(q[j]); f[j]=q[j];}for( j=0;j<= n;j++)a[1,j]=j;//第一个项目 投资j获得最大利益时, 给第一个项目 分配的资源数 第6讲 动态规划for( k=2;k<=m;k++)//阶段划分, 处理第二个项目到第m个项目{ for( j=0;j<= n;j++){ temp[j]=q[j]; input(q[j]); a[k][j]=0;}//temp用来记录正在计算的最大利益for( j=0 ;j<= n;j++)for( i=0 ;i<=j;i++)if(f[j i]+ [i]>tif(f[j-i]+q[i]>temp[j]) //如果大于temp则替换当前值{ temp[j]=f[j-i]+q[i]; a[k,j]=i; }for(j=0;j<= n;j++)f[j]=temp[j]; }rest=n;for(i=m;i>=1;i--){ gain[i]=a[i][rest]; rest=rest-gain[i];}for(i=1;i<=m;i++) print(gain[i],” ”);print(f[n]);}[j]) //如果大于t则替换当前值对第2到第m个项目进行决策对m个项目分配资源数输出投资方案 That’ s all for todaySee you next timeGood bye!

关注我们

关注微信公众号

您选择了以下内容