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