最优性原理对0/1背包问题成立： 设y1y2,,yn是X1,X2,Xn的0/1值最优序列。 若y1=0,KNAP(2,n,M)是初始决策产生的状态。则y2,.,yn 相对于KNAP(2,n,M)将构成一个最优序列。否则，y1y2,yn将 不是KNAP(1,n,M)的最优解 若y1=1,KNAP(2,n,M一w1)是初始决策产生的状态。则 y2,,yn相对于KNAP(2,n,M一w1)将构成一个最优序列。 否则，设存在另一0/1序列z1,22,2n,使得 ∑w,≤M-w 且 ∑p,a,≥∑p,y 2si≤n 2≤i≤n 2≤isn 则序列y1,z2,,Zn将是一个对于KNAP(1,n,M)具有更大效益 值的序列，与假设矛盾 故，最优性原理成立 2023/4/282023/4/28 最优性原理对0/1背包问题成立： 设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