KNAP(1,n,M)问题的解 ★Sn是KNAP(1,n,X)在0sX≤M各种取值下的最优解 ★KNAP(1,n,M)的最优解由Sn的最后一对有效序偶给出。 x的推导 xn:设Sn的最后一对有效序偶是(P,W),则 (P,W)或者是Sn-的最末一对序偶， 或者是(P+pn,W+wn),其中 (P,W)∈Sn-1且W是Sn-1中满足W+wnM的最大值。 ●若(P,W)∈Sn-1,则Xn=0;否则， ●(P-pn,W-wn)∈Sn-1,Xn=1 xn1:若xn=0,则判断(P,WW∈Sn-2?,.以确定X1的值 若xn=1,则依据(P一pn,Wwn)∈Sn-2?,以判断Xn1的值 Xn-2,X1将依次推导得出KNAP(1,n,M)问题的解 ★ Sn是KNAP(1,n,X)在0≤X≤M各种取值下的最优解 ★ KNAP(1,n,M)的最优解由Sn的最后一对有效序偶给出。 xi的推导 xn : 设Sn的最后一对有效序偶是(Pl ,Wl )，则 (Pl ,Wl )或者是Sn－1的最末一对序偶， 或者是(Pj+pn ,Wj+wn )，其中 (Pj ,Wj )∈ Sn－1且Wj是Sn－1中满足Wj+wn≤M的最大值。 ● 若(Pl ,Wl )∈ Sn－1，则Xn ＝0；否则， ● (Pl－pn ,Wl -wn )∈ Sn－1 ，Xn ＝1 xn-1 : 若xn=0，则判断(Pl ,Wl )∈ Sn－2？，以确定Xn-1的值 若xn=1，则依据(Pl－pn ,Wl -wn )∈ Sn－2？，以判断Xn-1的值 xn-2 ,…,x1将依次推导得出