How this proof of fractional knapsack works?

Question

I don't understand a step in my book proving the fractional knapsack problem:

Let value of items $v_1\ge v_2\ge \dots\ge v_n$, and assume $X=\langle x_1, \dots,x_n\rangle$ are the solution by greedy, where $0\le x_i\le 1$ is the fraction packed into the knapsack.

Assume $j$ is the first index s.t. $x_j<1$. Let $Y=\langle y_1,\dots, y_n\rangle$ be any solution not $X$.

Consider $$\dfrac{v_i}{w_i}(x_i-y_i)\ge\dfrac{v_j}{w_j}(x_i-y_i),\tag{????}$$

So $\displaystyle\sum_{i=1}^n v_i(x_i-y_i)=\sum\color{blue}v_i\dfrac{w_i}{\color{blue}w_i}(x_i-y_i)\ge\color{blue}{\dfrac{v_j}{w_j}}\sum w_i(x_i-y_i)\ge0.$

I can understand the blue part I highlighted, but can anyone help me understand the (????) part? Why it must hold?

Answer 1

The following condition is implicitly included in the question.

$$\dfrac{v_1}{w_1}, \dfrac{v_2}{w_2}, \cdots, \dfrac{v_n}{w_n} \text{ is in the descending order.}$$

Let $W$ be the total weight to be filled. The greedy algorithm for fractional knapsack problem is the following procedure.

Let $k$ loop through $1, 2, ..., n$ in that order.

1. Set $$x_k = \dfrac{W- \sum_{1\le i\lt k} x_i}{w_i}$$
2. If $x_k<1$, set $x_l=0$ for all $l>k$. Break the loop.

---

$$\dfrac{v_i}{w_i}(x_i-y_i)\ge\dfrac{v_j}{w_j}(x_i-y_i),\tag{????}$$

There are three cases for $i$.

• The case when i < j, i.e., $\dfrac{v_i}{w_i}\ge\dfrac{v_j}{w_j}$. Since $j$ is the first index s.t. $x_j<1$, $x_i=1$, i.e., $x_i-y_i\ge0$.

• The case when i = j. Both sides are 0.

• The case when i > j, i.e., $\dfrac{v_i}{w_i}\le\dfrac{v_j}{w_j}$. Since $j$ is the first index s.t. $x_j<1$, according to the definition of the greedy algorithm, $x_i=0$. That means $x_i-y_i\le0$.