0
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Apass.Jack Jan 1 at 6:02
  • $\begingroup$ 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. $\endgroup$ – Bit_hcAlgorithm Jan 1 at 6:07
  • 1
    $\begingroup$ 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$". $\endgroup$ – Apass.Jack Jan 1 at 6:08
  • 1
    $\begingroup$ 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. $\endgroup$ – Apass.Jack Jan 1 at 6:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.