increase in weight = wk (zk - yk)
decrease in weight = i=k+1 to n (yi - zi)wi

weight must stay the same so,

increase in profit = (zk - yk) pk
decrease in profit = i=k+1 to n (yi - zi)pi

If increase > decrease
then new Z is optimal as well.

So: WANT increase > decrease which is:

(zk - yk) pk       >?       i=k+1 to n (yi - zi)pi

OR (take each side and divide and multipy by the same term - will need this form)

(zk - yk) pk/wk * wk       >?       i=k+1 to n (yi - zi)pi/wi * wi

A > B

We KNOW the following (and it will be useful):
             pk/wk     >     pi/wi , k < i < n, (ordered that way for our greedy strategy)
          multiply both sides by the same terms
            i=k+1 to n (yi - zi)*pk/wk * wi     >    i=k+1 to n (yi - zi)*pi/wi * wi

C > B

OK, we now need to SHOW

A > C

What was A and what was C?

(zk - yk) pk/wk * wk       >?       i=k+1 to n (yi - zi)pk/wk * wi

(zk - yk)wk * pk/wk      >?       pk/wk i=k+1 to n (yi - zi)wi

divide both sides by pk/wk      note that what is left is the relation about weights that had to stay the same

SO, we showed A > C , we knew C > B and thus A > B

Therefore profit increase      >       decrease.       back to notes page