Step 1 : Find profit per weight ratio for each item and sort items on decreasing $\frac P W$ ratio.
$\frac P W =\frac{\left \{ 11,21,31,33,43,53,55,65 \right \}}{\left \{01,11,21,23,33,43,45,55 \right \}} = \left \{ \frac {11} 1,\frac {21} {11},\frac {31} {21},\frac {33} {23} ,\frac {43} {33},\frac {53}{43},\frac {55}{45},\frac {65} {55} \right \} $
$= \left \{1+ \frac {10} 1,1+\frac {10} {11},1+\frac {10} {21},1+\frac {10} {23} ,1+\frac {10} {33},1+\frac {10}{43},1+\frac {10}{45},1+\frac {10} {55} \right \}$
$= \left \{ 11,1.909,1.476,1.434,1.3030,1.232,1.222,1.181 \right \}$
we can see here that the ratio are already sorted in descending order so we will just choose items sequentially ,
Step 2 :
Algorithm after sorting items :
- If weight of 1st item in sorted list $\leq $ Sack capacity $M$
- Remove 1st item from sorted list and add it to sack.
- Decrease sack capacity by weight of added item,
- Increase profit by value of added item.
- Repeat above steps until item can be added. i.e Until ( $W_i>M$ or $M=0$ )
Initialize : $M=110 , P=0$
Add Item $I_1 \rightarrow $
$M=M-W_1=110-1=109,$
$P=P+P_1=0+11=11$
Add Item $I_2 \rightarrow M=98,P=32$
Add Item $I_3 \rightarrow M=77,P=63$
Add Item $I_4 \rightarrow M=54,P=96$
Add Item $I_5 \rightarrow M=21,P=139$
Note : Greedy algorithm for 0/1 KS may not give optimal solution, if the question was asking to solve 0/1 KS using greedy approach we would stop here as $W_6>M$ and answer $P=139$
Step 3 : If question asks to solve fractional KS we would add fraction of item $I_6$.
$\frac {P_6} {W_6} \times M = \frac {53} {43} \times 21 =25.884$
$\therefore$ adding $\frac {21} {43}$ of item $I_6 \rightarrow$
$M=M-W_1\times \frac {21} {43}=21-21=0,$
$P=P+P_1\times \frac {21} {43}=139+25.884=164.884$
