资源描述：
《背包问题详解.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。
1、动态规划系列之二背包问题彭智朝2010.6.81解空间设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）。2解空间图示以3个物品为例,解(0,1,0)表示(不取物品0,取物品1,不取物品2)root01010101030-1背包问题问题陈述：给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为c。问应如何选择装
2、入背包中的物品，使得装入背包中物品的总价值最大？在选择装入背包的物品时，对每种物品i只有两种选择，即装入背包或不装入背包。不能将物品i装入背包多次，也不能只装入部分的物品i。因此，该问题称为0-1背包问题。解题思路：此问题可转化为：给定c>0，wi>0，vi>0，1≤i≤n，要求找出一个n元0-1向量(x1，x2，…，xn)，xi∈{0，1}，1≤i≤n，使得∑wixi≤c，而且∑vixi达到最大。因此，0-1背包是一个特殊的整数规划问题：max∑vixis.t.∑wixi≤c，xi∈{0，1}，1≤i≤n可用动态规划算法求解。4其
3、他类型背包问题完全背包问题(0/1)：有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。多重背包问题有N种物品和一个容量为V的背包。第i种物品最多有n[i]件可用，每件费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。50-1背包问题设所给0-1背包问题的子问题的最优值为m(i，j)，即m(i，j)是背包容量为j，可选择物品为i，i+1，…，n时0-1
4、背包问题的最优值。由0-1背包问题的最优子结构性质，可以建立计算m(i，j)的递归式如下。算法复杂度分析：从m(i，j)的递归式容易看出，算法需要O(nc)计算时间。当背包容量c很大时，算法需要的计算时间较多。例如，当c>2n时，算法需要Ω(n2n)计算时间。60/1背包问题可以看作是决策一个序列(x1,x2,…,xn)，对任一变量xi的决策是决定xi=1还是xi=0。在对xi-1决策后，已确定了(x1,…,xi-1)，在决策xi时，问题处于下列两种状态之一：（1）背包容量不足以装入物品i，则xi=0，背包不增加价值；（2）背包容量
5、可以装入物品i，则xi=1，背包的价值增加了vi。这两种情况下背包价值的最大者应该是对xi决策后的背包价值。令V(i,j)表示在前i(1≤i≤n)个物品中能够装入容量为j（1≤j≤C）的背包中的物品的最大值，则可以得到如下动态规划函数：0-1背包问题71、0-1背包问题—动态规划算法voidKnapsack(int*v,int*w,intc,intn,int**m){intj;intjMax;if(w[n]-1>c)jMax=c;elsejMax=w[n]-1;for(j=0;j<=jMax;j++)m[n][j]=0;for(j=
6、w[n];j<=c;j++)m[n][j]=v[n];for(inti=n-1;i>1;i--){intjMax;if(w[n]-1>c)jMax=c;elsejMax=w[n]-1;for(j=0;j<=jMax;j++)m[i][j]=m[i+1][j];for(j=w[i];j<=c;j++)if(m[i+1][j]>m[i+1][j-w[i]]+v[i])m[i][j]=m[i+1][j];elsem[i][j]=m[i+1][j-w[i]]+v[i];}m[1][c]=m[2][c];if(c>=w[1])m[1][c]=
7、((m[1][c]>m[2][c-w[1]]+v[1])?m[1][c]:m[2][c-w[1]]+v[1]);}8根据动态规划函数，用一个(n+1)×(C+1)的二维表V，V[i][j]表示把前i个物品装入容量为j的背包中获得的最大价值。例如，有5个物品，其重量分别是{2,2,6,5,4}，价值分别为{6,3,5,4,6}，背包的容量为10。0123456789100w1=2v1=61w2=2v2=32w3=6v3=53w4=5v4=44w5=4v5=651、0-1背包问题—动态规划算法举例90123456789100000000
8、0000w1=2v1=6100666666666w2=2v2=3200669999999w3=6v3=5300669999111114w4=5v4=44006699910111314w5=4v5=6500669912121515150
