Return to 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?

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?

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?

Sorry I cannot provide the name of this book it's not written in English, but I'm sure I typed exactly the same as it says.

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?

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?

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?

Sorry I cannot provide the name of this book it's not written in English, but I'm sure I typed exactly the same as it says.