# proof of correctness for greedy knapsack algorithm

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

• 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.W.
Jun 7, 2018 at 0:00
• @D.W. I edited the post and the attached image. Jun 7, 2018 at 6:35

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.