第3章动态规划3-4节-0-1背包问题

动态规划

第3章 动态规划(Dynamic Programming).—3.4 0-1背包问题 0-

动态规划

0-1背包问题给定n种物品和一背包。物品i的重量是wi,其价值为vi, 背包的容量为C。问:应如何选择装入背包的物品，使得装 入背包中物品的总价值最大? 0-1背包问题描述:给定c >0, wi >0, vi >0 , 1≤i≤n.要求找一n 元向量(x1,x2,…,xn,), xi∈{0,1}, ∑ wi xi≤c,且∑ vi xi达最 大.即一个特殊的整数规划问题。max ∑ vi xii =1 n

n ∑ wi xi ≤ C s.t i =1 xi ∈{0,1},1 ≤ i ≤ n

(3.4.1)

动态规划

1.最优子结构(最优性原理)最优性原理:设(y1,y2,…,yn)是 (3.4.1)的一个最优解.则 最优性原理 (y2,…,yn)是下面相应子问题的一个最优解: nmaxn

∑v xi i =2

i

证明:使用反证法. 证明 若不然,设(z2,z3,…,zn)是上述子问题的一个最优解,而 (y2,y3,…,yn)不是它的最优解.显然有 ∑ vizi > ∑ viyi (i=2,…,n) 且 w1y1+ ∑ wizi ≤ c 因此 v1y1+ ∑ vizi (i=2,…,n) > ∑ viyi, (i=1,…,n) 说明(y1,z2, z3,…,zn)是(3-4-1)0-1背包问题的一个更优解,导出 (y1,y2,…,yn)不是背包问题的最优解,矛盾.

wx ≤C w y ∑ i i 1 1 s.t i =2 xi ∈{0,1}, 2 ≤ i ≤ n

动态规划

2.递归关系设所给0-1背包问题的子问题max

∑vk=i

n

k xk

(3.4.2)

n wk xk ≤ j s .t . k =i x ∈ {0,1}, i ≤ k ≤ n k

∑

的最优值为m(i,j),即m(i,j)是背包容量为j,可选择物品为i, i+1,…,n时0-1背包问题的最优值。由0-1背包问题的最优子 结构性质，可以建立计算m(i,j)的递归式:j ≥ wi max{m( i + 1, j ), m ( i + 1, j w i ) + v i } m( i , j ) = (3.4.3) 0 ≤ j < wi m ( i + 1, j )

j ≥ wn v n m ( n, j ) = (3.4.4) 0 0 ≤ j < wn4

动态规划

(1) max{m(i + 1, j ), m(i + 1, j wi ) + vi } j ≥ wi m(i, j ) = (3.4.3) 0 ≤ j < wi (2) m(i + 1, j ) (1) vn j ≥ wn m(n, j ) = (3.4.4) 0 0 ≤ j < wn (2)

注:(3-4-3)式 此时背包容量为j,可选择物品为i。此时在对xi作出决策之后,问题 3.算法复杂度分析 算法复杂度分析： 3.算法复杂度分析： 处于两种状态之一: 从m(i,j)的递归式容易看出，算法Knapsack需要 背包剩余容量是j,没产生任何效益; O(nc)计算时间; Traceback需O(n)计算时间 ；算法 剩余容量j-wi,效益值增长了vi . 总体需要O(nc)计算时间。当背包容量c很大时，算 从n推至i+1,i算出最优值m(i,j) ( i=n,…,1)n。 m(1,c)为最优值。 法需要的计算时间较多。例如，当c>2 时，算法需 然后用回溯法Traceback找出最优解xi 其中i,c为整值。 要 (n2n)计算时间。

动态规划

4.算法描述

背包问题的动态规划 算法Knapsack如下： 如下： 算法 如下

template< class Type > void Knapsack( Type v, int w, int c, int n, Type **m) { int jMax = min(w[n]-1, c) //背包剩余容量 背包剩余容量// 背包剩余容量 for(int j = 0; j<=

jMax; j++) //背包不同剩余容量 ≤ jMax<c// 背包不同剩余容量j 背包不同剩余容量 m[n][j]=0; for(int j=w[n]; j<=c; j++) //背包不同剩余容量 >c// 背包不同剩余容量j 背包不同剩余容量 m[n][j]=v[n]; for(int i=n-1; i>1; i--) { jMax=min(w[i]-1, c); for(int j=0; j<=jMax; j++) //背包不同剩余容量 ≤ jMax<c// 背包不同剩余容量j 背包不同剩余容量 m[i][j]=m[i+1][j]; //没产生任何效益 没产生任何效益// 没产生任何效益 for(int j=w[i]; j<=c; j++) //背包不同剩余容量 背包不同剩余容量j-wi >c// 背包不同剩余容量 m[i][j]=max(m[i+1][j], m[i+1][j-w[i]]+v[i]); //效益值增长 i // 效益值增长v 效益值增长}

动态规划

4.算法描述m[1][c]=m[2][c]; if(c>=w[1]) m[1][c]=max(m[1][c], m[2][c-w[1]]+v[1]); } Template < class Type >//求最优解 i // 求最优解x void Traceback(Type **m, int w, int c, int n, int x) { Knapsack算法的另一 算法的另一 算法 for(int i=1; i<n; i++) 缺点是要求所给物品 if(m[i][c]==m[i+1][c]) x[i]=0; 的重量w 的重量wi(1 ≤ i ≤ n) else { x[i]=1; 是整数 c= c- w[i]; } x[n]=(m[n][c])?1:0; } 说明:当wi为正整数时，用二维数组m[][]来存储m(i,j)相应的最 说明 优值。7

动态规划

5.改进算法 PP.71~PP.72为克服以上缺点，引入阶梯函数。利用序偶概念，改 进算法的计算时间复杂性为O(2n )。而当所给物品的重量 wi是整数时，其计算时间复杂性为 O(min{nc, 2n }) (略) 。 动态规划的其他应用实例(略) 旅行商问题 矩阵连乘问题 系统可靠性设计 流水线调度问题 设备更新问题 最优二叉搜索树 图像压缩8

动态规划

动态规划缺陷： 动态规划缺陷 (1)无一统一标准模型可供应用。利用“最优性原理”得出递归 关系式后，必须结合问题的特点，结合其他数学技巧求解，且无 统一处理方法。 (2)数值求解中，当问题中的状态变量个数太多(如有向图中的 边数),由于计算机存储量及计算速度限制而无法对付“维数障 碍”。 由前述可知，任一多阶段决策过程中的最优化问题，都可以用非 线性规划方法(Nonlinear programming Methods,特殊：linear programming)模型来描述。 动态规划的优越之处: 动态规划的优越之处 (1)易于确定全局解。动态规划方法是一种逐步改善的方法，它 把原问题化成一系列结构相似的最优化子问题，而每个子问题的 变量个数比原问题少的多，约束集合也简单得多，故较易于确定 全局最优。特别当处理离散类型问题时，动态规划是求出全局最 优化解的唯一方法。 (2)能得一族解，有利分析结果是否有用或进行选择(决策), 且大大节省工作量。 (3)能利用经验，提高求解效率。动态规划方法反映过程逐段演 变的前后联系，与实际进程更紧密，因而在计算中能… 9 (4)有广泛应用

背景(略)

动态规划

5.算法改进由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]={(0,0)}。10

动态规划

典型例子( 典型例子(一)n=3,c=6,w={4,3,2},v={5,2,1}。m(4,x) (0,0) m(4,x-2)+1 (2,1) m(3,x) (2,1) (0,0)

xm(3,x) (2,1) (0,0) m(3,x-3)+2 (3,2)

xm(2,x) (5,3) (0,0) (3,2) (2,1) (5,3)

x

xm(2,x) (3,2) (2,1) (5,3)

xm(2,x-4)+5 (7,7) (6,6) (4,5) (9,8) m(1,x)

x(7,7) (6,6) (4,5) (3,2) (5,3) (0, 0) (2, 1) (9,8)

(0,0)

x

x

x

动态规划

5.算法改进 函数m(i,j)是由函数m(i+1,j)与函数m(i+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)|(j,m(i,j))∈p[i+1]} 另一方面，设(a,b)和(c,d)是p[i+1]∪q[i+1]中的2个跳跃点， 则当c≥a且d<b时，(c,d)受控于(a,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,v4)={(5,4),(9,10)}。从跳跃点集p[5]与q[5]的并集 p[5]∪q[5]={(0,0),(4,6),(5,4),(9,10)}中看到跳跃点(5,4)受控于跳 跃点(4,6)。将受控跳跃点(5,4)清除后，得到 p[4]={(0,0),(4,6),(9,10)} q[4]=p[4]⊕(6,5)={(6,5),(10,11)} p[3]={(0,0),(4,6),(9,10),(10,11)} q[3]=p[3]⊕(2,3)={(2,3),(6,9)} p[2]={(0,0),(2,3),(4,6),(6,9),(9,10),(10,11)} q[2]=p[2]⊕(2,6)={(2,6),(4,9),(6,12),(8,15)} p[1]={(0,0),(2,6),(4,9),(6,12),(8,15)} p[1]的最后的那个跳跃点(8,15)给出所求的最优值为m(1,c)=15。 13

动态规划

算法复杂度分析上述算法的主要计算量在于计算跳跃点集 p[i](1≤i≤n)。由于q[i+1]=p[i+1]⊕(wi,vi),故计算 q[i+1]需要O(|p[i+1]|)计算时间。合并p[i+1]和 q[i+1]并清除受控跳跃点也需要O(|p[i+1]|)计算时 间。从跳跃点集p[i]的定义可以看出，p[i]中的跳 跃点相应于xi,…,xn的0/1赋值。因此，p[i]中跳跃 点个数不超过2n-i+1。

由此可见，算法计算跳跃点 集p[i]所花费的计算时间为 O ∑ | p[i + 1] | = O ∑ 2 = O(2 ) 从而，改进后算法的计算时间复杂性为O(2n)。当 所给物品的重量wi(1≤i≤n)是整数时，|p[i]|≤c+1, (1≤i≤n)。在这种情况下，改进后算法的计算时间 复杂性为O(min{nc,2n})。n n n i n i =2 i =2