f(X)=maxff1(X),f1(X-wi)+pi) 4例用动态规划法求解0/1背包问题 n=3,(W1,w2,w3)=(2,3,4),(p1,P2,P3)=(1,2,5),M=6 递推计算过程 {g X<0 X20 w=f X<0 max{0,一∞+1}=0 0≤X<2 max{0,0+1}=1 X22 X<0 0 0≤X<2 f2(X)=〈1 2≤X<3 max{1,0+2}=2 3≤X<5 max{1,1+2}=3 X25 f3(M)=max3,1+5)=64例用动态规划法求解0/1背包问题 n=3,(w1 ,w2 ,w3 )=(2,3,4),(p1 ,p2 ,p3 )=(1,2,5)，M=6 递推计算过程 －∞ X＜0 f0 (X)= 0 X≥0 －∞ X＜0 max{0,－∞+1}=0 0≤X＜2 max{0,0+1} = 1 X≥2 －∞ X＜0 0 0≤X＜2 1 2≤X＜3 max{1,0+2}=2 3≤X＜5 max{1,1+2} = 3 X≥5 f3 (M)= max{3,1+5} = 6 fi (X) = max{fi-1 (X),fi-1 (X-wi)+pi} f1(X)= f2(X)=