必威体育精装版算法设计与分析(霍红卫)-第3章-动态规划教学讲义PPT课件.ppt

算法设计与分析(霍红卫)_第3章动态规划;3.1用表代替递归;图3-1计算斐波那契数算法的递归结构（n=7）;利用自底向上的动态规划设计策略，我们可以将计算斐波那契数的递归算法(例2-1)变成以下的C语言函数：;自顶向下的动态规划(topdowndynamicprogramming)方法甚至是更简单的一种技术，它执行递归函数的运行时间与自底向上的动态规划的运行时间相同，有时更少。我们跟踪递归程序，存储它计算的每一个值，并检查计算的值，以避免重复计算。这种自顶向下的技术也称为备忘录(memoization)方法。利用自顶向下的动态规划设计策略，我们可以将计算斐波那契数的递归算法(例2-1)变成以下的C语言函数：;intfibarr［1000］={0};

intMEMOIZED-F(intn)

{intt;

if(fibarr［n］!=0returnfibarr［n］;

if(n==0)t=0;

if(n==1)t=1;

if(n1)t=MEMOIZED-F(n-1)+MEMOIZED-F(n-2);

returnfibarr［n］=t;

};图3-3计算斐波那契数的自顶向下的动态规划示例(n=7);算法将数组fibarr初始化为0，算法执行完成后，数组fibarr中的值如下所示：;3.20-1背包问题;图3-40-1背包问题示例;(1)刻画0-1背包问题最优解的结构。

我们可以将背包问题的求解过程看做是进行一系列的决策过程，即决定哪些物品应该放入背包，哪些物品不放入背包。

如果问题的一个最优解x1,x2,…,xn包含物品n，即xn=1，那么其余决策x1,x2,…,xn-1一定构成子问题1,2,…,n-1在容量为W-wn时的最优解。我们可以利用“切割—粘贴”方法证明：如果存在子问题1,2,…,n-1在容量为W-wn时的更大价值的解x1′,x2′,…,xn-1′，我们可以构造问题的一个新解x1′,x2′,…,xn-1′，xn。这个解比x1,x2,…,xn的总价值更大，这与x1,x2,…,xn是问题最优解相矛盾。如果这个最优解不包含物品n，即xn=0，那么这个最优解一定包含子问题1,2,…,n-1在容量为W时的最优解。证明过程类似上述情形。;(2)递归定义最优解的值。

根据子问题的最优解递归地定义问题最优解的开销。设c［i,w］表示背包容量为w时，i个物品导致的最优解的总价值。显然，问题的最优价值为c［n,W］。由(1)中分析可得，c［i,w］递归定义如下：;(3)计算背包问题最优解的值。

基于上述计算c［i,w］的递归方程，我们很容易写一个递归算法RECURKNAP，计算背包容量为W时n个物品的最优价值。然而，这个算法为指数时间复杂度O(2n)，并不比穷举法好。;我们不是直接计算递归方程的解，而是利用一个表格，以自底向上的方式计算最优价值。过程KNAPSACK-DP以物品权值〈w1，w2,…,wn〉，物品价值〈v1,v2，…,vn〉，物品个数n，背包容量W作为输入，并将c［i,w］的值存储在辅助表c［0..n,0..W］中，以行为主序从左到右计算表c中的元素。同时维持辅助表s［1..n,1..W］，以简化最优解的构造。为简单起见，我们只将物品个数及背包容量在参数表中列出。;KNAPSACK-DP(n,W)

1forw←0toW

2doc［0,w］←0

3fori←1ton

4doc［i,0］←0

5forw←1toW

6doifw［i］≤w

7thenifv［i］+c［i-1,w-w［i］］c［i-1,w］

8thenc［i,w］←v［i］+c［i-1,w-w［i］］

9elsec［i,w］←c［i-1,w］

10elsec［i,w］←c［i-1,w］;由算法