背包问题讲解文稿.ppt

背包问题讲解文稿.ppt

《背包问题讲解文稿.ppt》由会员分享，可在线阅读，更多相关《背包问题讲解文稿.ppt（15页珍藏版）》请在冰点文库上搜索。

算法案例0-1背包问题,通信四班刘蕾、文艺蓉、周家欣,2/15,0-1背包问题,问题描述：

给定n种物品和一背包。

物品i的重量是wi，其价值为vi，背包的容量为c。

问应如何选择装入背包中的物品，使得装入背包中物品的总价值最大？

0-1背包问题：

对每种物品i装入背包或不装入背包。

不能将物品i装入背包多次，也不能只装入部分的物品i。

3/15,0-1背包问题,解空间：

设Xi表示第i件物品的取舍，1代表取，0代表舍，搜索的空间为n元一维数组（X1,X2,X3,，Xn）,取值范围：

为（0，0，0，0，0），（0，0，0，0，1），（0，0，0，1，0），（0，0，0，1，1），（1，1，1，1，1）。

4/15,0-1背包问题,解空间图示：

以3个物品为例,解（0,1,0）表示（不取物品0,取物品1,不取物品2）,5/15,0-1背包问题,问题转化：

给定c0，wi0，vi0，1in，要求找出一个n元0-1向量（x1，x2，xn），xi0，1，1in，使得wixic，而且vixi达到最大。

6/15,0-1背包问题,由0-1背包问题的最优子结构性质，可以建立计算m（i，j）的递归式如下：

设所给0-1背包问题的子问题的最优值为m（i，j），即m（i，j）是背包容量为j，可选择物品为i，i+1，n时0-1背包问题的最优值。

第i+1个物品不装入背包,第i+1个物品装入背包,第i+1个物品无法装入背包,7/15,0-1背包问题,voidKnapsack（intv,intw,intc,intn,intm）intn=v.length-1;intjMax=Math.min（wn-1,c）;for（j=0;j1;i-）intjMax=Math.min（wi-1,c）;for（j=0;j=w1）m1c=Math.max（m1c,m2c-w1+v1）;,M,横坐标表示所放物品号码，纵坐标表示背包容量1到C，值表示当前考虑方案的价值,不选择第i个物品,如何可以装下（重量允许）,选择价值更大的方式（装入or不装入）,处理边界情况,处理边界情况,8/15,0-1背包问题,问题实例：

有5个物品，其重量分别是2,2,6,5,4，价值分别为6,3,5,4,6，背包的容量为10。

mij表示把第i,.,n物品装入容量为j的背包的最大价值,9/15,0-1背包问题,问题实例：

有5个物品，其重量分别是2,2,6,5,4，价值分别为6,3,5,4,6，背包的容量为10。

m5=4=6,mij表示把第i,.,n物品装入容量为j的背包的最大价值,intjMax=Math.min（wn-1,c）;for（j=0;j=jMax;j+）mnj=0;for（j=wn;j=c;j+）mnj=vn;,10/15,0-1背包问题,问题实例：

有5个物品，其重量分别是2,2,6,5,4，价值分别为6,3,5,4,6，背包的容量为10。

容量为5的背包，考虑是否装入物品4,mij表示把第i,.,n物品装入容量为j的背包的最大价值,for（inti=n-1;i1;i-）intjMax=Math.min（wi-1,c）;for（j=0;j=jMax;j+）mij=mi+1j;for（j=wi;j=c;j+）mij=Math.max（mi+1j,mi+1j-wi+vi）;,11/15,0-1背包问题,问题实例：

有5个物品，其重量分别是2,2,6,5,4，价值分别为6,3,5,4,6，背包的容量为10。

mij表示把第i,.,n物品装入容量为j的背包的最大价值,12/15,0-1背包问题,voidKnapsack（intv,intw,intc,intn,intm）intn=v.length-1;intjMax=Math.min（wn-1,c）;for（j=0;j1;i-）intjMax=Math.min（wi-1,c）;for（j=0;j=w1）m1c=Math.max（m1c,m2c-w1+v1）;,m,横坐标表示背包号码，纵坐标表示背包容量1到C，值表示当前考虑方案的价值,背包容量0-wn-1，该物品装不下,n个物品,背包装不下物品n，此时考虑物品n装入方法最大价值为零,背包能装下物品n，物品n装入方法最大价值为vn,背包不能装下物品时,背包能装下物品时,图示,隐藏,Traceback求最优解,TemplateVoidTraceback（Type*m,intw,intc,intn,intx）for（inti=1;in;i+）if（mic=mi+1c）xi=0;elsexi=1;c-=wi;xn=（mnc）?

1:

0;,13/15,按照Knapsack计算后m1c给出的为0-1背包问题的最优值，然后按照上述Traceback算法构造出最优解（x1,x2,x3,xn）。

14/15,0-1背包问题,Traceback回溯过程：

综上所述：

本例中最大价值为15，最优解向量为（1,1,0,0,1）,1,1,0,0,1,15/15,Thanku,