算法设计与分析第7讲 背包问题.ppt

《算法设计与分析第7讲 背包问题.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、0-1背包问题给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大?0-1背包问题是一个特殊的整数规划问题。1背包问题的应用1.一辆货车有固定的载重量C，有n种货物，每种货物i的重量和价格是（wi,vi）,运输哪些货物有最大的收益；2.一个计算机有内存C,有n个程序，分别耗费内存及其所交费用是（wi,vi）,调度哪些程序，使得费用最大；2最优子结构性质设所给0-1背包问题的一个最优解是(y1,y2,…,yn),则（y2,y3,…yn）是右面的子问题的最优解否则，存在（

2、z2,z3,..zn）,满足约束条件，并且那么(y1,z2,z3…zn)，满足原问题的约束，并且那么(y1,y2,…,yn)就不是原问题的最优解了3最优子结构性质最优子结构说明：一个n阶的问题，可由一个n-1阶的问题得到。以P(n,C)记录一个n阶，容量为C的问题,最优价值F(n,C)，(y1,…yn)为最优解，则如yn=1,(y1,…yn-1)是P(n-1,C-wn)的最优解，从而F(n,C)=F(n-1,C-Wn)+vn如果yn=0,（y1,…yn-1）是P(n-1,C)的最优解，从而F(n,C)=F(n-1,C)。因此，F(n,C)=ma

3、x(F(n-1,C-wn)+Vn,F(n-1,C)4递归树F(n,C)=max(F(n-1,C-wn)+Vn,F(n-1,C)--------如果C<0,F(n,C)=-∞F(n,C)F(n-1,C-wn)F(n-1,C)F(n-2,C-Wn-Wn-1)F(n-2,C)F(n-2,C-wn)F(n-2,C-wn-1)动态规划－自底向上计算5F(n,C)=max(F(n-1,C-wn)+Vn,F(n-1,C)--------如果C<0,F(n,C)=-∞n=5，c=10，w={2，2，6，5，4}，v={6，3，5，4，6}c=012345678

4、910n=100666666666n=200669999999n=300669999111114n=4006699910111314n=50066991212151515回溯构造解ifF(n,c)=F(n-1,c)xn=0,elsexn=1;ifxn=0,由F(n-1,c)继续构造xn-1,else由F(n-1,c-wn)构造x5=1,x4=0,x3=0,x2=1,x1=1.算法例6复杂性计算矩阵元素需要nC次，故时间不仅与n相关，还与C相关。当C比较大时，如C=2n,就是一个指数复杂性。那么，把C，w1,w2,…都除以某个数，时间变小？但是能

5、满足他们除了结果都是整数才行。另外，根据递归树，每一层实际上并不需要计算C个。时间还可以缩小。7结束8最优子结构性质设所给0-1背包问题的子问题的最优值为m(i，j)，即m(i，j)是背包容量为j，可选择物品为i，i+1，…，n时0-1背包问题的最优值。由0-1背包问题的最优子结构性质，可以建立计算m(i，j)的递归式如下。9m(n,1),m(n,2),…m(n,C)m(n-1,1),m(n-1,2),…m(n-1,C)…..m(1,1),m(1,2),…m(1,C)其中，m(1,C)就是所求10算法Knapsack(Typev,intw[],

6、intc,intn,Type**m){jMax=min(w[n]-1,c)For(j=0;j1;i--){jmax=min(w[i]-1,c);For(j=0,j=w[1])m[1][c]=max

7、(m[1][c],m[2][c-w[1]]+v[1]);}11计算最优值算法及其复杂性算法描述：P72算法复杂度分析：从m(i，j)的递归式容易看出，算法需要O(nc)计算时间。当背包容量c很大时，算法需要的计算时间较多。例如，当c>2n时，算法需要Ω(n2n)计算时间。实际上m(i,j)中的j跟wi相关，并不需要用到[1,C]的紧密分布,其中很多j没有用到。12算法改进由m(i,j)的递归式容易证明，在一般情况下，对每一个确定的i(1≤i≤n)，函数m(i,j)是关于变量j的阶梯状单调不减函数。跳跃点是这一类函数的描述特征。在一般情况下，函数

8、m(i,j)由其全部跳跃点惟一确定。如图所示。对每一个确定的i(1≤i≤n)，用一个表p[i]存储函数m(i，j)的全部跳跃点。表p[i]可依计算m(