Problem $3$ Fractional Knapsack

$5pts.$

Consider a fractional Knapsack problem with $n$ divisible itcms, where $v_i$ and $w_i$ are the value and weight of the $i^{th}$ item respectively. Assume the size of the Knapsack is $W.$

$($a$)$ Design an optimal greedy algorithm, i$.$c$.$ model the fractional Knapsack as a multi$-$stage decision problem $($clearly define the state, decision, outcome and reward variables, and the greedy decision philosophy based on a myopic score used to optimize at each stage.$)(3$ pts$)$

$($b$)$ Prove the correctness of your greedy algorithm for the fractional Knapsack problem. $(2$ pts$)$

Solution $3($a$)$

Multi$-$Stage Decision Problem Model: At the $K^{\frac{l}{h}}$ stage, we have

State $s_K$ :

Decision $x_K^{}$ :

Outcome $y_K$ :

Reward $u_K$ :

Mypoic $($Greedy$)$ Decision:

Pseudocode:

GreedyFracknapsack $($items$)$ :