# How this proof of fractional knapsack works?

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?

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$$.

• The condition "$v_1\ge v_2\ge \dots\ge v_n$" should be $\dfrac{v_1}{w_1}\ge\dfrac{v_2}{w_2}\ge \cdots\ge\dfrac{v_n}{w_n}$ instead. – John L. Jan 1 '19 at 6:02
• So it seems like the condition $\dfrac{v_1}{w_1}\ge\dfrac{v_2}{w_2}\ge \cdots\ge\dfrac{v_n}{w_n}$ is actually not needed? Only need to know $x_j$ is the last one greedy choose. – Bit_hcAlgorithm Jan 1 '19 at 6:07
• Yes, if we change "Assume $j$ is the first index s.t. $x_j<1$" to "Assume $j$ is the only index s.t. $x_j<1$". – John L. Jan 1 '19 at 6:08
• It should be "Assume $j$ is the only index s.t. $0<x_j<1$". But it might happen all $x_k$ are either 1 or 0. So it looks like there is some problem with your book or your formulation of the question. (It seems my answer is valid.) Anyway, I would believe you have understood what is happening here. – John L. Jan 1 '19 at 6:18