3 从前向后求解的递推关系式 记f()是KNAP(1,jX)的最优解，则fnM) 是KNAP(1,n,M)的最优解 对于fn(M)有： fn(M)=maxffn-1(M),fn-1(M-Wn)+pn} 第N个物品不放入 第N个物品放入 Xn=0 Xn=1 对于任意的f(X),>0,有 fi(X)max{fi1(X),fi1(X-wi)+pi}
3 从前向后求解的递推关系式 记fj (X)是KNAP(1,j,X)的最优解，则fn (M) 是KNAP(1,n,M)的最优解 对于fn (M)有： fn (M) = max{fn-1 (M), fn-1 (M-wn )+pn } 对于任意的fi (X)，i＞0,有 fi (X) = max{fi-1 (X),fi-1 (X-wi )+pi } 第N个物品不放入 xn=0 第N个物品放入 xn=1
递推过程： ★初始值 0 X≥0 X<0 Af (X)=max {fo(X),fo(X-W)+P} 求出所有可能的X对应的f值 *fi(X)=max {fi-1(X),fi-1(X-Wi)+Pi} ★最后求fn(M)=KNAP(1,n,M)
递推过程： ★初始值 0 X≥0 f0（X）= －∞ X＜0 ★f1(X)=max{f0(X),f0(X-W1)+P1} 求出所有可能的X对应的fi值 ★fi(X)=max{fi-1(X),fi-1(X-Wi)+Pi} ★最后求 fn (M)=KNAP(1,n,M)
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)=6
4例用动态规划法求解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)=