proof of correctness for greedy knapsack algorithm

Question

I don't really understand why is statement 1 ≥ statement 2 in the attached picture. From what I understand the negative term in statement 2 must be greater than or equal the negative term in statement 1 if statement 1 ≥ statement 2 but I don't really know how. Any help on this matter will be really appreciated. Thanks!

Statement 1 and Statement 2 refers to the red highlighted boxes, from the attached picture, tagged as 1 and 2 respectively.

Original source: http://oucsace.cs.ohiou.edu/~razvan/courses/cs4040/lecture15.pdf

enter image description here

• D.W.: I don't understand what you mean by statement 1 ≥ statement 2. What is statement 1? What does it mean for one statement to be greater than or equal to another?
• D-PUNK-R: @D.W. I edited the post and the attached image.

Answer 1

Slides are not a substitute for a textbook or careful exposition. This is especially true when reading a proof. Slides are intended for presentation in real-time, and as a result often leave out some details. If there is some aspect you don't understand when reading a set of slides, usually the best thing to do is to find a proper written exposition of the subject -- usually a textbook (but sometimes written lecture notes can be adequate, if written in enough detail).

In this case, on the previous slide, the statement of the theorem mentions "nonincreasing order of $p_i/w_i$", which means that $p_1/w_1 \ge p_2/w_2 \ge \cdots$. In particular, $p_k/w_k \ge p_i/w_i$ when $k<i$. The inequality you are referencing then follows.

• D-PUNK-R: Ok, I get it now. Thanks a lot. Those slides are not from my school. I just found the slides on the internet. I usually rely on the book but the book I am using in my university doesn't even include the proof. So, I started looking for it on the internet and I found a lot of proofs that were confusing to me, but I was able to grasp this one a lot better than the other ones so I decided to stick to this one.