最优性原理对0M背包问题成立: ●●●●● ●●●● ●●0 设y1y2;yn是x12x2…,xn的0/值最优序列。 ●●● ●●●● 若y1=0,KNAP(2n,M是初始决策产生的状态。则y2,yn 相对于KNAP(2n,M)将构成一个最优序列。否则,y1y2,yn将 不是KNAP(1,n,M)的最优解 若y1=1,KNAP(2n,M-w是初始决策产生的状态。则 y2,yn相对于KNAP(2,n,MW1)将构成一个最优序列。 否则,设存在另一01序列z1z2…,zn,使得 2;≤M-W 且 11y < 2≤i<1 则序列y1z2…,zn将是一个对于KNAP(1n,M)具有更大效益 值的序列,与假设矛盾 故,最优性原理成立 2021/282021/2/8 最优性原理对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