You have a shipping container that can hold $W$ worth of weight $($please ignore volume$).$ You have $n$

types of items that you can ship. You have $w_i$ pounds of item $i,$ and item i has a value of $v_i$ dollars

per pound. However, you can take a fraction of any item, so if you wanted, you could pack $p{w}_i$

pounds of item i$,$ which would be worth $p{w}_i{v}_i$ dollars, where ${\displaystyle \underset{\phantom{}}{\overset{\phantom{}}{}}}{\displaystyle \underset{\phantom{}}{\overset{\phantom{}}{}}}f{\displaystyle \underset{\phantom{}}{\overset{\phantom{}}{}}}{\displaystyle \underset{\phantom{}}{\overset{\phantom{}}{}}}ffm1,$dots,$m0.$ You would like $to$ pack

the shipping container $so$ that the total value $isas$ large $as$ possible.

Consider a greedy algorithms that evaluates a function ${\displaystyle \underset{\phantom{}}{\overset{\phantom{}}{}}}$for each item. Then the algorithm puts $as$

much $of$ the largest $as$ much $of$ the largest ${\displaystyle \underset{\phantom{}}{\overset{\phantom{}}{}}}-$valued item into the container $as$ possible. $If$ there $is$ still

room remaining, the algorithm goes $to$ the next largest $f-$valued item, and $soon.$

$(a)$ What function ${\displaystyle \underset{\phantom{}}{\overset{\phantom{}}{}}}$should you use $to$ rank items? $(Don\text{'}t$ overthink $it!)$

$(b)$ Let's rename the itms according $to$ their ${\displaystyle \underset{\phantom{}}{\overset{\phantom{}}{}}}$score $so$ that item $1$ has the highest $f-$score, item

$2$ the $2nd$ highest, and $soon.(You$ may assume all $f-$values are unqiue.$)To$ make the proof

$as$ simple $as$ possible, you can suppose that with the optimal strategy $we$ are always able $to$ fit

exactly all $of$ the first $m$ items into the shipping container, but not more. Prove using a proof

$by$ contradiction that any other strategy that doesn't put all $of$ items $1,$dots,$m$ into the container

$is$ not optimal. $(Itis$ probably somewhat obvious that this greedy strategy $is$ optimal $-$ the point

$of$ this problem $isto$ practice this proof strategy.$)$

$(c)$ What $is$ the runtime $of$ this greedy algorithm?