Consider the following greedy algorithm Alg$1$ to solve the Knapsack prob$$ lem:

Order all the items ai in non$-$increasing order of their density, which is the ratio of value to size, vi $.$ Make a single pass through the list, from highest to lowest density.

si

For each item encountered, if it still fits, include it$,$ otherwise exclude it$.$

Prove that algorithm Alg$1$ does not guarantee any constant approximation ratio. That

is$,$ for any positive integer k$,$ there is an input to the algorithm for which the total value

of the set of items returned by the algorithm is at most vOpt $.$