2.最优化原理证明 设y1y2,yn是×1，X2,,Xn的0/1值最优序列。 若y1=0,KNAP(2,n,M)是初始决策产生的状态。则 y2yn相对于KNAP(2,n,M)将构成一个最优序列。否则， y1y2,yn将不是KNAP(1,n,M)的最优解 若y1=1,KNAP(2,n,M一w1)是初始决策产生的状态。 则y2yn相对于KNAP(2,n,M一w1)将构成一个最优序列。 否则，设存在另一0/1序列z1,Z2,乙n,使得∑w,2≤M-w 2≤i≤n 且 ∑p,,≥∑py 2≤i≤n 2≤i≤n 则序列y1,z2,,Zn将是一个对于KNAP(1,n,M)具有更大 效益值的序列。 故，最优性原理成立设y1 ,y2 ,…,yn是x1 ,x2 ,…,xn的0/1值最优序列。 若y1＝0, KNAP(2,n,M)是初始决策产生的状态。则 y2 ,…,yn相对于KNAP(2,n,M)将构成一个最优序列。否则， y1 ,y2 ,…,yn将不是KNAP(1,n,M)的最优解 若y1＝1, KNAP(2,n,M－w1 )是初始决策产生的状态。 则y2 ,…,yn相对于KNAP(2,n,M－w1 )将构成一个最优序列。 否则，设存在另一0/1序列z1 ,z2 ,…,zn ,使得 且 则序列y1 ,z2 ,…,zn将是一个对于KNAP(1,n,M)具有更大 效益值的序列。 故，最优性原理成立     − i n wi zi M w 2 1        i n i n i i i i p z p y 2 2 2.最优化原理证明