0
$\begingroup$

The following algorithm is given:

Algorithm FractionalKnapsack(S,W):
Input: Set S of items, such that each item i∈S has a positive benefit b_i and a positive 
weight w_i; positive maximum total weight W
Output: Amount x_i of each item i ∈ S that maximizes the total benefit while not exceeding 
the maximum total weight W. 
for each item i∈S
    x_i<-0
    v_i<-b_i/w_i // value index of item i
w<-0
while w<W do
      remove from S an item i with highest value index // greedy choice
      a<-min{w_i,W-w} // more than W-w causes a weight overflow
      x_i<-a
      w<-w+a

According to my lecture notes:

To see that the fractional knapsack problem satisfies the greedy-choice property, suppose that there are two items $i$ and $j$ such that $$x_i<w_i,\ \ \ x_j>0, \ \ \ \text{ and } v_i<v_j$$

Let $y=\min \{ w_i-x_i, x_j\}$.

We could then replace an amount $y$ of item $j$ with an equal amount of item $i$, thus increasing the total benefit without changing the total weight.

Therefore, we can correctly compute optimal amounts for the items by greedily choosing items with the largest value index.

Could you explain me the idea of the proof?

Why does the following hold?

We could then replace an amount $y$ of item $j$ with an equal amount of item $i$, thus increasing the total benefit without changing the total weight.

I haven't understood it.

EDIT: Why do we deduce from the following:

We could then replace an amount $y$ of item $j$ with an equal amount of item $i$, thus increasing the total benefit without changing the total weight.

that the fractional knapsack problem satisfies the greedy-choice property?

$\endgroup$
1
$\begingroup$

It holds as, if the case assumed in the text (for contradiction) happens for a valid solution $x_1,\dots,x_n$ of the fractional Knapsack (where $x_k$ represents the fraction of the weight $w_k$ added to the Knpasack in that solution), then the following holds. You have a quantity $y>0$ of item $j$ in your solution (as $y \leq x_j$ by definition) and can still add at least a quantity $y$ of item $i$ to your knapsack before "using all the available quantity" of item $i$) (as $y \leq w_i - x_i$ by definition). So you can swap the quantity $y$ of item $j$ you have for the same quantity of item $i$ (formally decrease $x_j$ by $y$, and increase $x_i$ by $y$), this will still satisfy the constraints.

But the new overall value $V^\prime$ will become greater than the previous value $V$, as $V^\prime = V - y\cdot v_j +y\cdot v_i$; and $v_i > v_j$ (and $y>0$) by assumption.

$\endgroup$
  • $\begingroup$ Could you explain me further the following? $$$$ You have a quantity $y>0$ of item $j$ in your solution. $$$$ How can we be sure that $j$ should be contained in the knapsack? Or do we assume so? $\endgroup$ – evinda Jun 7 '15 at 17:32
  • $\begingroup$ You start with a solution $x_1,\dots, x_n$. The argument goes by showing that if there are items $i,j$ such that $x_i < w_i$, $x_j > $ and $v_j < v_i$, then this solution can be improved (and would be by the greedy algorithm). And since we have $x_j > 0$ and $x_i < w_i$, the quantity $y$ as defined is such that $x_j \geq y > 0$, so in particular there is a fraction $y$ of the weight $w_j$ in the solution we are trying to improve. $\endgroup$ – Clement C. Jun 7 '15 at 17:39
  • $\begingroup$ $v_j < v_i$ (I believe there is a typo in your lecture notes, it should be $v_j < v_i$) only ensures that the new solution has higher value. $\endgroup$ – Clement C. Jun 7 '15 at 17:43
  • $\begingroup$ So can the solution be improved because of the fact that w could replace several times the item $j$ with the item $i$? And can we say this, although we are given no information about $w_i$ and $w_j$? $$$$ Also what does $y$ represent ? The current weight contained in the knapsack? Or something else? $\endgroup$ – evinda Jun 7 '15 at 17:54
  • 1
    $\begingroup$ I will stop answering now. Look at how $v_k$ is defined: $v_k=\frac{b_k}{w_k}$, so what I wrote and what you wrote are the same. $\endgroup$ – Clement C. Jun 7 '15 at 19:38

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.