Knapsack Greedy Approximation: Worst Case
The approximation ratio is always strictly larger than $1/2$. Let $p_1,\ldots,p_{k-1}$ be the values of the items picked by algorithm, and let $p_k$ be the value of the next item which would have been picked had it fit. Let $\alpha$ be the fraction of $p_k$ that does fit – so $\alpha &lt; 1$. These lecture notes (Claim 2) show that
$$ p_1 + \cdots + p_{k-1} + \alpha p_k \geq OPT, $$
where $OPT$ is the optimal solution. In particular,
$$ p_1 + \cdots + p_{k-1} + p_k &gt; OPT. $$
The algorithm picks either items $1,\ldots,k-1$ or only item $k$, and there is some choice that results in strictly more than $OPT/2$.