Understanding Greedy Choice Property of Fractional Knapsack Problem

[evinda]

Hello! (Wave)

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?

[m] 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. [/m]I haven't understood it.

 

[Future Bruno]

The idea of the proof is to show that the fractional knapsack problem satisfies the greedy-choice property, which means that the optimal solution can be obtained by making the best choice at each step. In this case, the best choice is the item with the highest value index. To do this, we consider two items $i$ and $j$, where $x_i < w_i$, $x_j > 0$, and $v_i < v_j$. This means that item $i$ has not been fully taken yet, and item $j$ has been partially taken, and item $i$ has a lower value index than item $j$. Now, let $y = \min \{w_i - x_i, x_j\}$. This means that the amount of item $j$ taken could be replaced with an equal amount of item $i$. Since the total weight remains unchanged, this would increase the total benefit since $v_i < v_j$. Thus, the optimal solution can be obtained by greedily choosing items with the highest value index.