$1\mathrm{.}1$ Fractional Knapsack $[8$ points$]$

Consider the fractional knapsack problem discussed in class. Suppose that for a given fractional

knapsack instance $($W$,$w$1,$ b$1,$

$,$wn$,$ bn$),$ we have already obtained an optimal solution x$$

$=$

$($x$$

$1,,$ x$$

n$)$ using the greedy algorithm discussed in class.

$($i$)(4$ points$)$ If the capacity of the knapsack doubles from W to $2$W $,$ how can we modify the

existing greedy solution x$=($x$$

$1,,$ x$$

n$)$ to obtain a new optimal solution $$

x$=($ x$$

$1,$

$,$

$$

x$$

n$)?$

Explain your idea first and then give your algorithm in pseudo code.

$($ii$)(4$ points$)$ If the capacity of the knapsack shrinks from W to W$/2,$ how can we modify the

existing greedy solution x$=($x$$

$1,,$ x$$

n$)$ to obtain a new optimal solution $$

x$=($ x$$

$1,$

$,$

$$

x$$

n$)?$

Explain your idea first and then give your algorithm in pseudo code.

For both questions above, assuming that you cannot re$-$run the greedy algorithm with an updated

capacity $($otherwise both questions would be trivial$).$