14背包问题 141背包问题及其串行算法 0-1背包问题(0-1 Knapsack Problem)的定义为:设集合A={a1,a2…,am}代表m件物 品正整数pw分别表示第i件物品的价值与重量,那么0-1背包问题KNAP(4c)定义为, 求A的子集,使得重量之和小于背包的容量c,并使得价值和最大。也就是说求 (16.1) 其中x∈{0,1}。 解决0-1背包问题的最简单的方法是动态规划( Dynamic Programming)算法。我们先 看看KNAP(4,)的一个子问题KNAP(A,y),其中A={a,a2…a},y≤c。显然,若a 并不在最优解中,那么KNAP(A1y)的解就是KNAP(A,y)的解。否则, KNAP(4=1,y-w)就是KNAP(4,y)的解。设∫(y)是KNAP(4,y)的最优解,我们得 到下面的最优方法: f6( 0jfy≥0 if y<o f(y)=max{1(y),f=(0y-)+p} nd1≤j≤m 设F(c)=(,(0),J(①),…,J(c)0≤j≤m,那么,动态规划算法就是依次地计 算F(c,F2(c)…Fm(C)来求解问题。其中F(c)是KNAP(4,c)的最大价值向量。 动态规划算法是基于 Bellman递归循环,它是求解决背包问题的最直接的方法。基于 (162)式我们可以写出串行算法如下 算法16.70-1背包问题的串行动态规划算法 输入:各件物品的价值pn…pm,各件物品的重量w,…wm,背包的容量c 输出:能够放入背包的物品的最大总价值fm(c) procedure Knapsack(p, w, c)8 1.4 背包问题 1.4.1 背包问题及其串行算法 0-1 背包问题（0-1 Knapsack Problem）的定义为：设集合 , , , 1 2 { } A a a a = m 代表 m 件物 品,正整数 , i r p w 分别表示第 i 件物品的价值与重量，那么 0-1 背包问题 KNAP(A,c)定义为, 求 A 的子集，使得重量之和小于背包的容量 c，并使得价值和最大。也就是说求： 1 1 max m i i i m i i i p x subject to w x c = =    (16.1) 其中 {0,1} i x  。 解决 0-1 背包问题的最简单的方法是动态规划（Dynamic Programming）算法。我们先 看看 KNAP(A，c)的一个子问题 KNAP( , A y j )，其中 1 2 { , , , }, A a a a y c j j =  。显然，若 j a 并 不 在 最 优 解 中 ， 那 么 KNAP 1 ( , ) A y j− 的 解 就 是 KNAP (A , y) j 的 解 。 否 则 ， KNAP ( , ) j 1 wj A − y − 就是 KNAP (A , y) j 的解。设 f ( y) j 是 KNAP (A , y) j 的最优解，我们得 到下面的最优方法： ( ) ( )  ( ) ( )  0 1 1 0 0 0 max , 0 1 j j j i j if y f y if y f y f y f y w p for all y c and j m − −   =  −  = − +     (16.2) 设 F (c) ( f (0), f (1), , f (c)) j j j  j  = 0  j  m ，那么，动态规划算法就是依次地计 算 ( ), ( ), , ( ) 1 2 F c F c F c m     来求解问题。其中 F (c) j  是 KNAP( Aj ，c)的最大价值向量。 动态规划算法是基于 Bellman 递归循环，它是求解决背包问题的最直接的方法。基于 (16.2)式我们可以写出串行算法如下： 算法 16.7 0-1 背包问题的串行动态规划算法 输入：各件物品的价值 p1,…,p.m，各件物品的重量 w1,…,wm，背包的容量 c。 输出：能够放入背包的物品的最大总价值 fm(c)。 procedure Knapsack(p, w, c) Begin