第25讲：动态规划.ppt

《第25讲：动态规划.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、动态规划2010/06/261回顾：数字三角形机器人捡垃圾最大连续子序列和最长递增子序列背包问题。2简单的背包问题(0-1背包)设有ｎ种物品，每种物品有一个重量及一个价值。同时有一个背包，最大载重量为M，今从ｎ种物品中选取若干件，使其重量的和小于等于m，而价值的和为最大。N<=100,M<1000.输入数据：第一行两个数：物品总数Ｎ，背包载重量M；两个数用空格分隔；第二行N个数,为Ｎ种物品重量Wi(<1000)；两个数用空格分隔；第三行N个数,为N种物品价值Vi(<1000);两个数用空格分隔；输出数据：总价值；

2、输入样例1：41043571572025输出样例1：35输入样例2：420291015291016输出样例2：1930123456789100000000000001000015151515151515200071515152222222230007152020222735354000715202025273535背包的容量0--10物品0--4编号1234容量4357价值15720254件物品背包容量：10算法：设f[i,j]:从1到i件物品中选若取干件放到容量为j的背包中，获得的最大价值。目标是：f[n,m]4用f

3、[i,j]表示在第１到第i件物品中装入重量为j的背包获得的最大价值．f[i,j]=max{f[i-1,j],f[i-1,j-W[i]]+V[i]}(1<=i<=n,1<=j<=m)目标：f[n,m];2)f[i-1,j-W[i]]+V[i]：放第i件的价值。条件：j>=w[i]1)f[i-1,j]:不放第i件物品获得的价值。5主程序：fillchar(f,sizeof(f),0);fori:=1tondoforj:=1tomdobeginf[i,j]:=f[i-1,j];//不选择第i件物品if(j>=w[i])and(f

4、[i,j]

5、使用，避免重复计算相同的子问题，从而提高程序运行的时间效率，这就是动态规划算法的优点。动态规划算法通常用于统计问题和最优化问题（最大值或最小值），尤其普遍用于最优化问题。7最短路径问题现在，我们想从城市A到达城市E。怎样走才能使得路径最短，最短路径的长度是多少？AB1B2C1C2C3C4D1D2D3E531638438556343一、动态规划的概念8阶段1阶段2阶段3阶段4阶段5第1部分：A第2部分：B1，B2第3部分：C1，C2，C3，C4第4部分：D1，D2，D3第5部分：EAB1B2C1C2C3C4D1D2D3E53

6、16384385563439定义f(i)为i点到E的最短距离，d(i,j)为节点i到节点j的距离。下面我们用动态规划的策略采取倒推的方法来求A到E的最短距离。第5阶段:f(E)=0;第4阶段:f(D1)=3;f(D2)=4;f(D3)=3第3阶段:f(C1)=min{d(C1,D1)+f(D1),d(C1,D2)+f(D2)}=min{8,10}=8f(C2)=d(C2,D1)+f(D1)=8f(C3)=d(C3,D3)+f(D3)=11f(C4)=d(C4,D3)+f(D3)=6第2阶段:f(B1)=min{d(B1,C

7、1)+f(C1),d(B1,C2)+f(C2),d(B1,C3)+f(C3)}=min{1+8,6+8,3+11}=9f(B2)=min{d(B2,C2)+f(c2),d(B2,C4)+f(C4)}=min{8+8,4+6}=10第1阶段:f(A)=min{d(A,B1)+f(B1),d(A,B2)+f(B2)}=min{5+9,3+10}=13最短路径：A->B2->C4->D3->E最短距离：13倒推法：10动态规划的术语：1、阶段：把所给求解问题的过程恰当地分成若干个相互联系的阶段，以便于按一定的次序去求解，过程不同

8、，阶段数就可能不同．描述阶段的变量称为阶段变量。在多数情况下，阶段变量是离散的，用k表示。阶段的划分一般根据时间和空间来划分的。2、状态：某一阶段的出发位置成为状态，通常一个阶段有多个状态。状态通常可以用一个或一组数来描述，称为状态变量。3、决策：一个阶段的状态给定以后，从该状态演变到下一阶段某个状态