动态规划与贪心策略.pptVIP

动态规划与贪心策略2个典型问题

背包与0-1背包0-1背包问题：

给定n种物品和一个背包。物品i的重量是Wi，其价值为Vi，背包的容量为C。应如何选择装入背包的物品，使得装入背包中物品的总价值最大?

在选择装入背包的物品时，对每种物品i只有2种选择，即装入背包或不装入背包。不能将物品i装入背包多次，也不能只装入部分的物品i。背包问题： 与0-1背包问题类似，所不同的是在选择物品i装入背包时，可以选择物品i的一部分，而不一定要全部装入背包，1≤i≤n。两题可否采用贪心策略解决？是否具有最优子结构？可否选择贪心策略？思路是什么？1.用贪心算法解背包问题的基本步骤首先计算每种物品单位重量的价值Vi/Wi，然后，依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。若将这种物品全部装入背包后，背包内的物品总重量未超过C，则选择单位重量价值次高的物品并尽可能多地装入背包。依此策略一直地进行下去，直到背包装满为止。 具体算法可描述如下页：算法knapsack的主要计算时间在于将各种物品依其单位重量的价值从大到小排序。当然，为了证明算法的正确性，还必须证明背包问题具有贪心选择性质。对于0-1背包问题，贪心选择之所以不能得到最优解是因为在这种情况下，它无法保证最终能将背包装满，部分闲置的背包空间使每公斤背包空间的价值降低了。事实上，在考虑0-1背包问题时，应比较选择该物品和不选择该物品所导致的最终方案，然后再作出最好选择。由此就导出许多互相重叠的子问题。此时使用贪心策略不能解决问题，而要使用动态规划算法求解。 动态规划动态规划基本原理一、多阶段决策问题如果一类活动过程可以分为若干个互相联系的阶段，在每一个阶段都需作出决策(采取措施)，一个阶段的决策确定以后，常常影响到下一个阶段的决策，从而就完全确定了一个过程的活动路线，则称它为多阶段决策问题。各个阶段的决策构成一个决策序列，称为一个策略。每一个阶段都有若干个决策可供选择，因而就有许多策略供我们选取，对应于一个策略可以确定活动的效果，这个效果可以用数量来确定。策略不同，效果也不同，多阶段决策问题，就是要在可以选择的那些策略中间，选取一个最优策略，使在预定的标准下达到最好的效果.例题1：如图所示的是一个带权有向的多段图，要求从A到D的最短路径的长度(下面简称最短距离)。有哪些信誉好的足球投注网站，枚举图中的每条路径，但当图的规模大起来时，有哪些信誉好的足球投注网站的效率显然不可能尽人意。重复计算多。第二种方法：从图中可以看到，A点要到达D点必然要经过B1和B2中的一个，所以A到D的最短距离必然等于B1到D的最短距离加上5，或是B2到D的最短距离加上2。同样的，B1到D的最短距离必然等于C1到D的最短距离加上3或是C2到D的最短距离加上2，……。我们设G[i]为点i到点D的距离，显然G[C1]=4，G[C2]=3，G[C3]=5，根据上面的分析，有：G[B1]=min{G[C1]+3，G[C2]+2}=5，G[B2]=min{G[C2]+7，G[C3]+4}=9，再就有G[A]=min{G[B1]+5，G[B2]+2}=10，所以A到D的最短距离是10，最短路径是A?B1?C2?D。二、动态规划的术语

1．阶段k把所给求解问题的过程恰当地分成若干个相互联系的阶段，以便于求解，过程不同，阶段数就可能不同．描述阶段的变量称为阶段变量。在前面的例子中，第一个阶段就是点A，而第二个阶段就是点A到点B，第三个阶段是点B到点C，而第四个阶段是点C到点D。2．状态sk状态表示每个阶段开始面临的自然状况或客观条件，称为不可控因素。例子中状态就是某阶段的出发位置，它既是该阶段某路的起点，同时又是前一阶段某支路的终点。第一个阶段有一个状态即s1={A}，而第二个阶段有两个状态s2=｛B1，B2｝，第三个阶段是三个状态s3={C1，C2,C3}，而第四个阶段又是一个状态s4={D}。状态通常可以用一个或一组数来描述，称为状态变量。状态之间的转移通过状态转移方程来表达,例子中，计算b1到d的最短路径，必须先在已经求出c1到d的最短路径和c2到d的最短路径的基础上才能求出。与其他城市特别是a城市无关。（无后效性）阶段i只能由i+1的状态通过状态转移方程得出，与其他状态无关，尤其是与未发生的状态无关。3．决策uk一个阶段的状态给定以后，从该状态演变到下一阶段某个状态的一种选择（行动）称为决策。决策的目的就是确定下一阶段状态。例子中：从阶段1b1出发的