$1$ The Knapsack Problem is defined as follows:

Instance: integer numbers $a_1,$dots,$a_n,$ and $b$

Output: $(x_1,$dots,$x_n)in\{0,1{\}}^n,$ such that

$(1)a_1{x}_1+$dots$+a_n{x}_{n}b$

$(2)W={\displaystyle \underset{i=1}{\overset{n}{}}}{a}_i{x}_i=ma{x}_{(y_1,\text{d}\text{o}\text{t}\text{s}\text{,}{y}_n)in\{0,1{\}}^n}\{a_1{y}_1+$dots$+a_n{y}_n|{\displaystyle \underset{i=1}{\overset{n}{}}}{a}_i{y}_{i}b\}$

Let $W_{\text{o}\text{p}\text{t}}(I)$ be the maximum value of $W$ for the instance I in the Simple Knapsack Problem.

A greedy algorithm A first sorts the numbers $a_1,$dots,$a_n$ in decreasing order and constructs a solution

in which at each step a maximum number $a_i$ is chosen which satisfies the condition $(1).$

Prove that the greedy algorithm A provides for the instance I a solution $L(A,I)$ with the cost

$W(A,I),$ such that $W_{\text{o}\text{p}\text{t}}\frac{\text{I}}{W}(A,I)2.$