0-1背包问题动态规划6讲解.ppt

动态规划（六） 0-1背包问题 问题描述：有 n 件物品x1, x2, …, xn , 每件物品有一个价值和一个重量，分别记为： v1,v2, …vn w1,w2, …wn 其中所有的 wi 均为整数。 现有一个背包，其最大载重量为m，要求从这n件物品中任取若干件（这些物品要么被装入要么被留下）。问背包中装入哪些物品可使得所装物品的价值和最大？ 例如，m=23, n = 5, vi : 19 24 33 45 50 wi : 5 6 8 11 12 分析 最优子结构性质分析： 我们首先自问一个简单的问题：在最优解中，是否包括了xi(I=1..n)？只可能有两种情况： 1. 包括有。那么何妨另起炉灶，换一个更简单的问题来思考：在背包载重为m-wi的情况下，在其它n-1件物品中挑选，更得价值和最大。等把这个子问题求出后，再加上vi的价值就是整个问题的最优解了。 2. 没包括。那么就当xi根本不存在，直接解物品数量为n-1，背包载重为m的子问题。子问题的最优解就是问题的最优解。 这样，我们就看出，无论那种情况，在问题的最优解中，都包含着子问题的最优解。 分析 递归地定义问题的解： 请思考本题各数据的存储结构？ 价值：一维数组v[1..n] 重量：一维数组w[1..n] 因为所求问题是n件物品，背包限重为m，随着问题规模的增减，n 和m都在变化，因此很自然地想到把件数和背包限重都作为自变量。定义函数f(i,j)为在1~I 件物品中选若干件装入限重为j的背包中的最大价值和。 那么根据前面的讨论中关于第I件物品是否装入了背包的情况分析，我们得出关系式： 当第I件物品要装入背包时，f(I,j) := I-1件物品，限重为j-w[I]的最优解+ v[I], 即： f(I,j) := f(I-1, j-w[I]) + v[I] 当然，第I件物品要装入是有条件限制的，是什么？ 第I件物品重量小于等于背包限重，即 w[I] = j 当第I件物品不装入背包时，f(I,j) := I-1件物品，限重为m的最优解，即： f(I,j) := f(I-1, j) 分析 现在已经求得装入或者不装入第I件物品的限重为J的背包的最大价值，那么接下来应该做什么？ 比较这两种情况下谁的价值更大，更大者为当前问题的最优解。 if f(I,j)’ f(I,j)’’ then f(I,j) := f(I,j)’ else f(I,j) := f(I,j)’’; 上述递归式的边界条件是什么？ 我们知道f(I,j)的I和J都有一个取值范围。1=I=n, 0 =J=m. 边界条件就是当问题规模缩小到自变量下界时的函数的取值情况。 当背包限重为0时，无法放任何物品，此时所有的f(I,0) := 0 (1=I=n). 这就是边界条件。 分析 根据上述递归式已经可以递归地求出最优解了。请自行编程练习。 下面按自底向上的方式求解本题。 在按自底向上的动态规划方式求解问题时，其实主要就是做一件事： 按问题规模从小到大地求解问题，把每阶段求得的问题的最优解保存在表格（数组）中，以便在下一阶段求解更大的问题时，可以直接查表引用子问题的最优解。 首先分析阶段。 将n件物品放入背包，故可以把阶段划分为n个。把在前I件物品中选取物品放入背包作为第I个阶段。 再分析状态。第I个阶段的状态J是对前I件物品进行取舍后得到的背包的重量。显然状态J满足条件0=J=m ，即是说状态J的取值范围在0到背包的最大限重之间。注意，由于物品重量均为正整数，所以状态J是0~m之间的整数，可以进行枚举。 分析 这样，在第I个阶段就有m+1个问题需要求解，分别是f[I,0], f[I,1], …,f[I,m]。由于前面分析可知所有的f[I,0]均为0，因此实际需要求解的是m个问题。 而这m个问题的求解基础是第I-1个阶段的m个子问题。这些子问题的最优解已经先于此时求得，保存在f[I-1,1], f[I-1,2], …, f[I-1,m]中，现在只需要直接引用它们的值就可以了。这就是动态规划自底向上的体现。 最后分析决策。前面的分析中已经明确了决策的个数，大家说是多少个？ 只有两个：在前I件物品中，限重为J的条件下，装入第I件物品还是不装入第I件物品。比较这两种情况的价值和，谁大谁就是最优解。 分析 总结一下： 阶段：1~n个 初始阶段：f[I,0] := 0 (1=I=n); f[0,m] := 0 状态：1~m个 决策：2个。 现在编程没有任何困难了吧。 分析 最优解的形成过程。我认为，所谓最优解的形成过程就是要记录每个阶段的各个状态的最优解是由哪个决策变量产生的。 在背包问题中，第I个阶段的限重为