动态规划-背包及最优二叉树ppt课件.pptx

《动态规划-背包及最优二叉树ppt课件.pptx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、0/1背包20-1背包问题所谓0/1背包问题是指在物品不能分割，只能整件装入背包或不装入的情况下，求一种最佳装载方案使得总收益最大.给定n种物品和一背包,物品编号从1到n。物品i的重量是wi，其价值为vi，背包的容量为C。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大.0-1背包问题是一个特殊的整数规划问题。最优子结构0/1背包的最优解具有最优子结构特性。设(x1,x2,…,xn)，xi{0,1}是0/1背包的最优解，那么，(x1,x2,…,xn-1)必然是0/1背包子问题的最优解：背包载重Cwnxn，共有n-1件物品，第i件物品的重量为wi，效益

2、Vi，wi>0，vi>0，1i

3、m[1，j]=3(第一种物品的价值)，当且仅当j≥2(第一种物品的体积)。第二行中的每项m[2,j]有两种可能性，第一种可能性是置m[2，j]=m[1,j]这相当于把第一种物品放入背包，２号物品放不下；第二种可能性是置m[2,j]=m[1,j-3]+4,它相当于加上第二种物品，使它或者仅包含第二种物品，或者同时包含第一种和第二种物品。当然，仅当j≥3时，才有可能加上第二种物品。继续这种方法，填入第3行和第4行，得到如图所示的表。例列号体积为2，3，4和5的物品，价值分别为3，4，5和7。容量为9的背包作业设有0/1背包问题n=3，（w1,w2,w3）=（2,3,4

4、），（v1,v2,v3）=（1,2,4）和C=6。Knapsack有两个较明显的缺点：1.算法要求所给物品的重量w是整数2.当背包容量c很大时，算法需要的计算时间比较多。9算法改进由m(i,j)的递归式容易证明，在一般情况下，对每一个确定的i(1≤i≤n)，函数m(i,j)是关于变量j的阶梯状单调不减函数。跳跃点是这一类函数的描述特征。在一般情况下，函数m(i,j)由其全部跳跃点唯一确定。如图所示。对每一个确定的i(1≤i≤n)，用一个表p[i]存储函数m(i，j)的全部跳跃点。表p[i]可依计算m(i，j)的递归式递归地由表p[i+1]计算，初始时p[n+1]=

5、{(0，0)}。10一个例子n=3，c=6，w={4，3，2}，v={5，2，1}。x(0,0)m(4,x)x(2,1)m(4,x-2)+1x(0,0)(2,1)m(3,x)(3,2)xm(3,x-3)+2(5,3)x(0,0)(2,1)m(2,x)(3,2)(5,3)xm(2,x-4)+5(4,5)(6,6)(7,7)(9,8)x(0,0)(2,1)m(1,x)(3,2)(5,3)(4,5)(6,6)(7,7)(9,8)x(0,0)(2,1)m(3,x)x(0,0)(2,1)m(2,x)(3,2)(5,3)11函数m(i,j)是由函数m(i+1,j)与函数m(i

6、+1,j-wi)+vi作max运算得到的。因此，函数m(i,j)的全部跳跃点包含于函数m(i+1，j)的跳跃点集p[i+1]与函数m(i+1，j-wi)+vi的跳跃点集q[i+1]的并集中。易知，(s,t)q[i+1]当且仅当wisc且(s-wi,t-vi)p[i+1]。因此，容易由p[i+1]确定跳跃点集q[i+1]如下q[i+1]=p[i+1](wi,vi)={(j+wi,m(i,j)+vi)

7、(j,m(i,j))p[i+1]}另一方面，设(a，b)和(c，d)是p[i+1]q[i+1]中的2个跳跃点，则当ca且d

8、b)，从而(c，d)不是p[i]中的跳跃点。除受控跳跃点外，p[i+1]q[i+1]中的其它跳跃点均为p[i]中的跳跃点。由此可见，在递归地由表p[i+1]计算表p[i]时，可先由p[i+1]计算出q[i+1]，然后合并表p[i+1]和表q[i+1]，并清除其中的受控跳跃点得到表p[i]。算法改进12一个例子n=5，c=10，w={2，2，6，5，4}，v={6，3，5，4，6}。初始时p[6]={(0,0)}，(w5,v5)=(4,6)。因此，q[6]=p[6](w5,v5)={(4,6)}。p[5]={(0,0),(4,6)}。q[5]=p[5](w4,

9、v4)={