因为ⅹ不是最优解,则存在解向量y=(y,y,……,y,使得 ∑Py>∑Px。不妨假定∑wx=M。设k是使得y≠x的最小 下标,则y<x.这是因为:当kj时,x=1,上述不等式自然成立 当k2j时,因为x=y,x2=y2,…,xk-=y-,当k<isn时,x1=0,所 以由y>x可推出∑1y>∑x=M,y不是解向量,矛盾 现在取新的向量z=(z1,z2,…,zn)满足 Z1=y1,Z2-y2,………,Zk-1=yk-1,Zk=Xn 0≤z=≤yk,…,0≤z≤y而且∑w;(v1-z,)=wk(zk-yk) k+l≤i≤ 这样的向量z是存在的,而且是0/1背包问题的解,因为 11=∑Wy1+Wk=k∑ :2 l≤i<n l<i≤k-1 k+l≤i<n ∑y1+∑W (5.5) l≤i≤k-1 k≤i≤n ∑wy1≤M l≤i<n 至此,我们找到一个新的解向量z。以下证明它的总价值不小于y的 总价值: ∑P1=∑Py+(=k-yk)形kPk/Wk-∑(y1-)wP1/w1 l≤i<n k<isn ≥∑Py+(=k-yk)k-∑(-=)m|p4/k(5.6) k+1≤i<n ∑Py 中间的不等式是由于当Ik时有p/w≥p1/w而得。但与x的不同分量 的个数比y与x的不同分量的个数至少减少一个。以z代替y进行上 面的讨论,我们又可以找到新的解向量z,如此等等,由于分量的个因为 x 不是最优解，则存在解向量 y=(y1,y2,⋅⋅⋅⋅⋅⋅,yn), 使 得 ∑ i i > ∑ i i p y p x 。不妨假定∑wi xi = M 。设 k 是使得 yk≠ xk的最小 下标，则 yk< xk. 这是因为：当 k<j 时，xk=1,上述不等式自然成立； 当 k≥j 时，因为 x1=y1, x2=y2,⋅⋅⋅⋅⋅⋅, xk-1= yk-1，当 k<i≤n 时，xi＝0，所 以由 yk> xk可推出∑wi yi > ∑wi xi = M ，y 不是解向量，矛盾。 现在取新的向量 z=(z1,z2,⋅⋅⋅⋅⋅⋅,zn)满足 z1=y1, z2=y2,⋅⋅⋅⋅⋅⋅, zk-1= yk-1, zk= xk 0≤zk+1≤yk+1, ⋅⋅⋅⋅⋅⋅, 0≤zn≤yn而且 ( ) ( ) 1 k k k k i n i i i ∑w y − z = w z − y + ≤ ≤ 这样的向量 z 是存在的，而且是 0/1 背包问题的解，因为 w y M w y w y w z w y w z w z i n i i k i n i i i k i i k i n k k i i i k i i i n i i = ≤ = + = + + ∑ ∑ ∑ ∑ ∑ ∑ ≤ ≤ ≤ ≤ − ≤ ≤ ≤ ≤ ≤ ≤ − + ≤ ≤ 1 1 1 1 1 1 1 (5.5) 至此，我们找到一个新的解向量 z。以下证明它的总价值不小于 y 的 总价值： ∑ ∑ ∑ ∑ ∑ ∑ ≤ ≤ ≤ ≤ + ≤ ≤ ≤ ≤ ≤ ≤ < ≤ =       ≥ + − − − = + − − − i n i i k k k i n k k k i i i i n i i i i k i n k k k k k i i i i n i i i n i i p y p y z y w y z w p w p z p y z y w p w y z w p w 1 1 1 1 1 ( ) ( ) / ( ) / ( ) / (5.6) 中间的不等式是由于当 I>k 时有 pk/wk≥pi/wi而得。但与 x 的不同分量 的个数比 y 与 x 的不同分量的个数至少减少一个。以 z 代替 y 进行上 面的讨论，我们又可以找到新的解向量 z'，如此等等，由于分量的个