1、背包问题之 PASCAL 递归动归精讲在 M 件物品取出若干件放在空间为 W 的背包里，每件物品的重量为 W1，W2Wn，与之相对应的价值为 P1,P2Pn。求出获得最大价值的方案。 注意：在本题中，所有的重量值均为整数。 算法分析： 对于背包问题，通常的处理方法是搜索。 用递归来完成搜索，算法设计如下： function make( i 处理到第 i 件物品 , j剩余的空间为 j:integer) :integer; 初始时 i=m , j=背包总容量 begin if i:=0 then make:=0; if j=w then (背包剩余空间可以放下物品 i ) r1:=make(i-
2、1,j-w)+v; (第 i 件物品放入所能得到的价值 ) r2:=make(i-1,j) (第 i 件物品不放所能得到的价值 ) make:=max(r1,r2) -别告诉 我学了这么多年一个max 函数不会编 end; 你别看这个递归 小小的 执行 make 差不多 2n 次 差不多就是那一种 每一个包选还是不选 这个算法的时间复杂度是 o(2n)，我们可以做一些简单的优化。 由于本题中的所有物品的重量均为整数，经过几次的选择后背包的剩余空间可能会相等，在搜索中会重复计算这些结点，所以，如果我们把搜索过程中计算过的结点的值记录下来，以保证不重复计算的话，速度就会提高很多。这是简单的“以空间
3、换时间 “。 我们发现，由于这些计算过程中会出现重叠的结点，符合动态规划中子问题重叠的性质。 同时，可以看出如果通过第 n 次选择得到的是一个最优解的话，那么第 n-1 次选择的结果一定也是一个最优解。这符合动态规划中最优子问题的性质。 下面一些动归的 主要给一些高级学者看看 你懂了 说明你蛮高级的 考虑用动态规划的方法来解决，这里的： 阶段是：在前 n 件物品中，选取若干件物品放入背包中； 状态是：在前 n 件物品中，选取若干件物品放入所剩空间为 w 的背包中的所能获得的最大价值； 决策是：第 n 件物品放或者不放； 由此可以写出动态转移方程： 我们用 fi,j表示在前 i 件物品中选择若干
4、件放在所剩空间为 j 的背包里所能获得的最大价值 fi,j=maxfi-1,j-wi+pi (j=wi), fi-1,j 这样，我们可以自底向上地得出在前 m 件物品中取出若干件放进背包能获得的最大价值，也就是 fm,w 请注意 我相信你肯定见过自上向底的 它们是有区别的 请注意 算法设计如下： table=38.59%trtdprocedure make; begin for i:=0 to w do f0,i:=0; for i:=1 to m do for j:=0 to w do begin fi,j:=fi-1,j; if (j=w) and (fi-1,j-w+vfi,j) the
5、n fi,j:=fi-1,j-w+v; end; writeln(fm,w); end; /td/tr/table请参考伪代码 自上到底的for i=1.N if 第 i 件物品是 01 背包 for v=V.0 fv=maxfv,fv-c+w; else if 第 i 件物品是完全背包 for v=0.V fv=maxfv,fv-c+w; 由于是用了一个二重循环，这个算法的时间复杂度是 o（n*w)。而用搜索的时候，当出现最坏的情况，也就是所有的结点都没有重叠，那么它的时间复杂度是 o（2n)。看上去前者要快很多。但是，可以发现在搜索中计算过的结点在动态规划中也全都要计算，而且这里算得更多（
6、有一些在最后没有派上用场的结点我们也必须计算），在这一点上好像是矛盾的。 事实上，由于我们定下的前提是：所有的结点都没有重叠。也就是说，任意 n 件物品的重量相加都不能相等，而所有物品的重量又都是整数，那末这个时候 w 的最小值是：1+2+22+23+2n-1=2n -1 此时 n*w2n，动态规划比搜索还要慢| 所以，其实背包的总容量 w 和重叠的结点的个数是有关的。 考虑能不能不计算那些多余的结点 那么换一种状态的表示方式： 状态是：在前 n 件物品中，选取若干件物品放入所占空间为 w 的背包中的所能获得的最大价值；阶段和决策：同上； 状态转移方程是： fi,j=maxfi-1,j-wi+
7、pi (j+wi=w) and (fi,ws=fi-1,ws-w+v) then begin 输出解； ws:=ws-w; end; end; writeln; end; 用这两种算法的前提是我们必须存住 fi,j 这一整个二维数组，但是如果用循环数组的话怎样输出解呢？ 显然，我们只需要存住一个布尔型的二维数组，记录每件物品在不同的状态下放或者不放就可以了。这样一来数组所占的空间就会大大降低。 解题收获： 1）在动态程序设计中，状态的表示是相当重要的，选择正确的状态表示方法会直接影响程序的效率。 2）针对题目的不同特点应该选择不同的解题策略，往往能够达到事半功倍的效果。像本题就应该把握住“所有的重量值均为整数“这个特点。
