动态规划

第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)能得一族解，有利分析结果 …… 此处隐藏：3149字，全部文档内容请下载后查看。喜欢就下载吧 ……