$2\mathrm{.}1$ Problem $3[15pts]$

Problem $3.$ Consider the Knapsack problem with the following inputs:

A list of items: $(v_1,w_1),$dots,$(v_n,w_n),$ where $v_i$ is the value and $w_i$ is the weight of the $i-$th item.

A weight limit $W.$

The goal is to select a subset Ssube$\{1,$dots,$n\}$ such that:

${\displaystyle \underset{\text{i}\text{i}\text{n}\text{S}}{\overset{?}{}}}{w}_{i}W$

maximizes the total value:

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

Consider the following greedy algorithm for this problem:

Order the items by their value$-$per$-$weight ratio, $\frac{v_i}{w_i},$ in descending order.

Select items in this order, adding them to $S$ as long as the total weight remains within the limit $W.$

Provide an example demonstrating that this greedy algorithm does not always yield the optimal solution.

Include the example, show the steps of the greedy algorithm on it$,$ and present a solution with a higher total value

that adheres to the weight limit$.$