Recall the knapsack problem $($sometimes called the $"0-1"$ knapsack problem$)$: you are given $n$

items, where the $i$ th item has weight $w_i$ and value $v_i($both non$-$negative integers$),$ and a non$-$

negative weight capacity $W$ of the knapsack. An optimal solution is a subset Ssube$\{1,2,$dots,$n\}$

of the items having maximum total value

${\displaystyle \underset{\text{i}\text{i}\text{n}\text{S}}{\overset{?}{}}}{v}_i$

under the constraint that the total weight is at most the knapsack capacity, i$.$e$.,$

${\displaystyle \underset{\text{i}\text{i}\text{n}\text{S}}{\overset{?}{}}}{w}_{i}W$ In this problem, we introduce the fractional variant of the knapsack problem, where one may

take any fraction $p_{i}in[0,1]$ of any item $i.$ Naturally, a $p_i-$fraction of item i weighs $p_i*w_i,$ and

has value $p_i*v_i.$ The goal is to maximize the total value of the selected fractional items. $($c$)$ Consider the following greedy algorithm for the fractional knapsack problem:

RelativelyGreedy: While there is still some unused knapsack capacity, choose an

item having the largest relative value $\frac{v_i}{w_i}($among those not considered yet$),$ and add

the largest possible fraction of that item $($up to the full item$)$ that will fit within the

remaining knapsack capacity.

In this part, you will prove that the RelativelyGREEDY algorithm is a correct algorithm

for the fractional knapsack problem. This is notable because we used a more complicated

dynamic programming algorithm to solve $0-1$ Knapsack, but the fractional variant admits

a much simpler greedy algorithm!

The setup for your correctness proof is as follows. Without loss of generality, suppose that

the items are in sorted order by relative value $r_i=\frac{v_i}{w_i},$ from largest to smallest $($the

algorithm considers them in this order$).$ Let ALG$=p_1,p_2,$dots,$p_n$ be the fractions of items

$1,2,$dots,$n$ chosen by the algorithm, respectively. $($So$,p_i=1$ if the algorithm chooses all of

item $i,$ and $p_i=0$ if it doesn't choose any of item $i.)$

Let OPT be an arbitrary optimal solution. If ALG$=$ OPT, then ALG is optimal, as

needed. So suppose that ALG $$ OPT, and consider the smallest index $j$ such that OPT

does not have exactly a $p_j-$fraction of item $j.$

You will construct another optimal solution $OP{T}^{\text{'}}$ whose fractions of the first $j$ items are

exactly $p_1,p_2,$dots,$p_j$ by modifying OPT, using an exchange argument.

Describe which fraction$($s$)$ of item$($s$)$ to exchange, and prove that $OP{T}^{\text{'}}$ meets the stated

requirements; this should include a proof that $OP{T}^{\text{'}}$ is a valid solution.