(1) for i=0 to c do fo(i=0 end for (2) fori=1 to m do 1)f(0)=0 (2.2) forj= 1 to c do ifw:≤ I then ifp;+ fi10j-Wi>f-10 then f()=f() end if d for End/*Knapsack * 可以看出,串行的动态规划算法需要占用很大的空间,其本质是 Bellman递归,最坏和 最好的情况下的时间差不多相同。虽然,它在问题规模比较小时,可以很好的解决问题,但 是,随着问题规模的扩大,串行动态规划算法就显得力不从心了。 142背包问题的并行算法 现在,我们要做的是把串行程序改成并行程序。首先,我们分析一下串行程序的特点。 注意到第(2.2)步的for循环,f()只用到上一步f(y)的值,而与同一个i循环无关,这样, 可以把第(22)步直接并行化。得到下面的并行算法: 算法1680-1背包问题的并行算法 输入:各件物品的价值p,…,pm,各件物品的重量w,…,wm,背包的容量c 输出:能够放入背包的物品的最大总价值fm(c) arallelKnapsack(p, w, c) Begin (1) for each processor0≤j≤cdof()=0 end for (2)for i=I to m pardo (2.1) for each processor 0<j<w, do f()=f1() end for (22) for each processor M1≤j≤cdo f,O)=max_(),f_(-w)+p) End/* ParallelKnapsack *9 （1）for i = 0 to c do f0(i) = 0 end for （2）for i = 1 to m do （2.1）fi(0) = 0 （2.2）for j = 1 to c do if wi  j then if pi + fi-1(j - wi) > fi-1(j) then fi(j) = pi + fi-1(j – wi) else fi(j) = fi-1(j) end if else fi(j) = fi-1(j) end if end for end for End /* Knapsack */ 可以看出，串行的动态规划算法需要占用很大的空间，其本质是 Bellman 递归，最坏和 最好的情况下的时间差不多相同。虽然，它在问题规模比较小时，可以很好的解决问题，但 是，随着问题规模的扩大，串行动态规划算法就显得力不从心了。 1.4.2 背包问题的并行算法 现在，我们要做的是把串行程序改成并行程序。首先，我们分析一下串行程序的特点。 注意到第（2.2）步的 for 循环，fi(j)只用到上一步 fi(y)的值，而与同一个 i 循环无关，这样， 可以把第（2.2）步直接并行化。得到下面的并行算法： 算法 16.8 0-1 背包问题的并行算法 输入：各件物品的价值 p1,…,p.m，各件物品的重量 w1,…,wm，背包的容量 c。 输出：能够放入背包的物品的最大总价值 fm(c)。 procedure ParallelKnapsack(p, w, c) Begin （1）for each processor 0  j c do 0 f j ( ) 0 = end for （2）for i = 1 to m pardo （2.1）for each processor 0 i  j w do 1 ( ) ( ) i i f j f j = − end for （2.2）for each processor w j c i   do 1 1 ( ) max{ ( ), ( ) } i i i i i f j f j f j w p = − + − − end for end for End /* ParallelKnapsack */