★最优性原理对01背包问题成立: 设y1,y2yn是x,x2,x的0/1值最优序列。 ●初始状态:KNAP(1n,M) ●初始决策:决定y等于1还是等于0 ★若y1=0,KNAP(2,n-1,M是初始决策产生的状态。则y2yn相 对于KNAP(2n-1,M)将构成一个最优序列。否则,y1y2…yn将不是 KNAP(1,n,M)的最优解 ★若y1=1,KNAP(2n-1,MW1)是初始决策产生的状态。则y2yn相 对于KNAP(2n-1,M-W)将构成一个最优序列 如若不然,设存在另一0序列z2,z3,…,z乙n,使得 且∑p,≥∑PB∑mE≤M-m 2≤i≤n 2<i<n 则序列y1,z2,,zn将是一个对于KNAP(1n,M)具有更大效益值得序列。 与假设矛盾 故,最优性原理成立 2021/2/202021/2/20 8 ★ 最优性原理对0/1背包问题成立： 设y1 ,y2 ,…,yn是x1 ,x2 ,…,xn的0/1值最优序列。 ●初始状态： KNAP(1,n,M) ●初始决策：决定y1等于1还是等于0 ★ 若y1＝0, KNAP(2,n-1,M)是初始决策产生的状态。则y2 ,…,yn相 对于KNAP(2,n-1,M)将构成一个最优序列。否则，y1 ,y2 ,…,yn将不是 KNAP(1,n,M)的最优解 ★若y1＝1, KNAP(2,n-1,M-w1 )是初始决策产生的状态。则y2 ,…,yn相 对于KNAP(2,n-1,M－w1 )将构成一个最优序列。 如若不然，设存在另一0/1序列z2 ,z3 ,…,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