(1) vn j wn m(n, j ) (3.4.4) 0 0 j wn (2)
注:(3-4-3)式 此时背包容量为j，可选择物品为i。此时在对xi 作出决策之后,问题处于两种状态之一: 背包剩余容量是j,没产生任何效益; 剩余容量j-wi,效益值增长了vi . 从n推至i+1, i算出最优值m(i, j) （ i=n,…,1） 。 m(1,C)为最优值。 然后用算法traceback找出最优解xi ，其中i，C为整值。
算法复杂度分析： 从m(i，j)的递归式容易看出，算法knapsack需 要O(nc)计算时间; traceback需O(n)计算时间 ； 算法总体需要O(nc)计算时间。当背包容量c很 大时，算法需要的计算时间较多。例如，当 c>2n时，算法需要Ω(n2n)计算时间。
0-1背包问题
问题实例： 有5个物品，其重量分别是{2, 2, 的容量为10。
0 1 2 3 4 5 6 7 8 9 10
0
w1=2 v1=6 w2=2 v2=3 w3=6 v3=5 w4=5 v4=4 w5=4 v5=6
1
2 3 4 5
0-1背包问题
问题实例： 有5个物品，其重量分别是{2, 2, 6, 5, 4}，价 值分别为{6, 3, 5, 4, 6}，背包的容量为10。
6
6
6
10
6
10
6
0-1背包问题
问题实例： 有5个物品，其重量分别是{2, 2, 6, 5, 4}，价 值分别为{6, 3, 5, 4, 6}，背包的容量为10。
统计结果：
5．改进算法
为克服以上缺点，引入阶梯函数。利用序偶概念，改进 算法的计算时间复杂性为O(2n )。而当所给物品的重量wi是 整数时，其计算时间复杂性为 O(min{nc, 2n }) （略） 。 动态规划的其他应用实例（略） 凸多边形最优三角剖分 多边形游戏 图像压缩 电路布线 流水作业调度 最优二叉搜索树
对比
• 4. 分治法与动态规划适用条件: ① 分治法：原问题具有最优子结构性质的前提下,分解出的 子问题都绝对相互独立. ② 动态规划：原问题具有最优子结构性质的前提下,分解出 的子问题并不相互独立,求解一个子问题可能要用到已经求解 过的子问题的解,子问题间具有重叠性,即适合具有重叠子问 题性质的原问题. • 5. 分治法与动态规划复杂度分析: ① 分治法因为对子问题进行了多次求解,所以效率比动态规 划低一点.(时间复杂度相对高) ② 动态规划求解需要将子问题的解保存下来,所以会比分治 法多用一些空间.(空间复杂度相对高)
当wi（1 i n） 0-1背包问题的动态规划算法Knapsack如下： 为正整数时，用二 void knapsack( int []v, int []w, int c, int [][]m) 维数组m[][]来存 { 储m(i, j)相应的最 int n = v.length-1; 优值。 int jMax = min(w[n]-1, c) //背包剩余容量// for(int j = 0; j<=jMax; j++) //背包装不下w[n]的情况// m[n][j]=0; for(int j=w[n]; j<=c; j++) //背包装得下w[n]的情况// 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++) //背包装不下w[i]的情况// m[i][j]=m[i+1][j]; //没产生任何效益// for(int j=w[i]; j<=c; j++) //背包装得下w[i]的情况// m[i][j]=max(m[i+1][j], m[i+1][j-w[i]]+v[i]); //效益值增长vi ？//
0 1
0 0 0
2
6 3 0
3
6 3 0
4
9 6 6
5
9 6 6
6
12 9 6
7
12 9 6
8
15 9 6
9
15 10 10
10
15 11 11
0
w1=2 v1=6 w2=2 v2=3 w3=6 v3=5 w4=5 v4=4 w5=4 v5=6
1
2 3 4 5
0 0 0
0
0
0
0
0
0
0
0
6
6
6
6
6
6
6
（2）能得一族解，有利分析结果是否有用或进行选择（决策）， 且大大节省工作量。 （3）能利用经验，提高求解效率。动态规划方法反映过程逐段 演变的前后联系，与实际进程更紧密。 （4）有广泛应用背景
对比
• 1. 分治法与动态规划主要共同点: 二者都要求原问题具有最优子结构性质,都是将原问题分而治 之,分解成若干个规模较小(小到很容易解决的程序)的子问题. 然后将子问题的解合并,形成原问题的解.
（2）数值求解中，当问题中的状态变量个数太多，由于计算机 存储量及计算速度限制而无法对付“维数障碍”。
总结
动态规划的优越之处:
（1）易于确定全局解。动态规划方法是一种逐步改善的方法， 它把原问题化成一系列结构相似的最优化子问题，而每个子 问题的变量个数比原问题少得多，约束集合也简单得多，故 较易于确定全局最优。特别当处理离散类型问题时，动态规 划是求出全局最优化解的唯一方法。
max
v x
i i 2
n
i
n wi xi C w1 y1 s.t. i 2 x {0,1}, 2 i n 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)不是背包问题的最优解,矛盾.
0 1 2 3 4 5 6 7 8 9 10
0
w1=2 v1=6 w2=2 v2=3 w3=6 v3=5 w4=5 v4=4 w5=4 v5=6
1
2 3 4 5
0 0 0 0 6 6 6 6 6 6 6
m[5][<4] = 0, m[5][>=4]=6
0-1背包问题
问题实例： 有5个物品，其重量分别是{2, 2, 6, 5, 4}，价 值分别为{6, 3, 5, 4, 6}，背包的容量为10。
}
3.算法描述
3.算法描述
m[1][c]=m[2][c]; //令m[1][c]=m[2][c]// if(c>=w[1]) //如果背包装得下w[1]// m[1][c]=max(m[1][c], m[2][c-w[1]]+v[1]); } void traceback(int [][]m, int []w, int c, int []x) //求最优解xi // { int n = w.length-1; for(int i=1; i<n; i++) knapsack算法的 if(m[i][c]==m[i+1][c]) x[i]=0; 一个缺点是要求 else { x[i]=1; 所给物品的重量 c= c- w[i]; } wi （1 i n） x[n]=(m[n][c]>0)?1:0; 是整数 } 说明:当wi为正整数时，用二维数组m[][]来存储m(i,j)相应的 最优值。
第3章 动态规划
(Dynamic Programming)
—3.4 0-1背包问题
0-1背包问题
问题描述： 给定n种物品和一背包。物品i的重量是wi， 其价值为vi，背包的容量为C。问应如何选择 装入背包中的物品，使得装入背包中物品的 总价值最大？
0-1背包问题： 对每种物品i装入背 包或不装入背包。不 能将物品i装入背包多 次，也不能只装入部 分的物品i。
• • • • • •
总结
动态规划算法适用于解最优化问题。 通常按以下几个步骤设计动态规划算法： （1）找出最优解的性质，并刻画其结构特征；
（2）递归地定义最优值；
（3）以自底向上的方式计算出最优值 （4）根据计算最优值时得到的信息，构造最优解。
总结
动态规划缺陷： （1）无一统一标准模型可供应用。利用“最优子结构性质”得 出递归关系式后，必须结合问题的特点，结合其他数学技巧 求解，且无统一处理方法。
2.递归关系
设所给0-1背包问题的子问题
n
max
v
k i
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背包问题的最优值。
2.递归关系
由0-1背包问题的最优子结构性质，可以建立计算 m(i，j)的递归式如下： 第i个物品装入背包
第i个物品不装入背包
(3.4.3)
j wi m(i 1, j ), m(i 1, j wi ) vi } max{ m(i, j ) 0 j wi m(i 1, j )
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达最大, 即一个特殊的整数规划问题。